Large Integer and Base Conversion Integer Parent Script

Added on 4/2/2004

Compatibilities:
D8_5

This item has not yet been rated

The lack of an unsigned integer type in Director creates difficulty in working with 32-bit pixels, as well as other tasks. This parent script uses list elements as integer places, so you can create a base 256 integer and access each 8-bit portion by accessing the list elements. Basic arithmetic and comparison operators are included. It also accomplishes base conversion. Execution is slow, but because it relies on lists, rather than strings, I expect it to be faster than string based methods. The slowness does make it impractical to use for converting images to a text friendly representation such as ASCII 85 encoding.

--Allows for arbitrarily large integer math (limited functions, feel free to add more) in Lingo
--Feel free to modify and use.
--Contact d.nelson@bluejade.com with any comments or corrections

--a base integer is defined as a list with at least one positive integer element.
--when displayed, each element of the list takes on a "decimal" place, but instead of base 10, we use
--the base defined in new().
--So if the base is 256, then [1, 3] = 256^1 * 1 + 256^0 * 3 = 256 + 3 = 259.
--A first element of -1 indicates that the integer is negative.
--This might make color math easy since when you need the different components, simply access
--the elements in the list.
--Note: all arithmetic concludes with simplifying the integer so that no zeros precede the first
--non-zero number on the left and zero is always positive.
--
--Base conversion is also available throught the convertBase(, ) method.

property p_base

on new me, anInteger
  --copyright © 2004 Daniel W. Nelson
  --anInteger is the base, which must be less than 2^31 - 1
  --for arbitrarily long integers, using a base of 256 is desirable.  it is especially good for 32-bit
  --colors, since the color components can be grabbed by accessing that element of the list.
  if voidP(anInteger) then anInteger = 256
  p_base = anInteger
  return me
end new

on getBase me
  --copyright © 2004 Daniel W. Nelson
  return p_base
end getBase

on convertBase me, baseInteger, newBase
  --copyright © 2004 Daniel W. Nelson

  resultingBaseInteger = []
  if not(baseInteger[1]) then --the integer is zero
    return [0]
  else if baseInteger[1] < 0 then
    resultIsNegative = TRUE
    baseInteger.deleteAt(1)
  else
    resultIsNegative = FALSE
  end if

  newBase = me.makeIntegerIntoBaseNumber(newBase) --convert newBase to a base integer in the current base so that it
  --can be run through the arithmetic operators

  --compute the smallest power that, dividing anInteger by the p_base raised to that power gives zero with
  --integer division
  divisor = newBase
  power = 1
  repeat while me.divide(baseInteger, divisor)[1] <> 0
    divisor = newBase
    power = power + 1
    repeat with j = power - 1 down to 1
      divisor = me.multiply(divisor, newBase)
    end repeat
  end repeat
  --end: compute the smallest power that...

  repeat with i = power down to 1
    divisor = [1]
    repeat with j = i - 1 down to 1
      divisor = me.multiply(divisor, newBase)
    end repeat
    thisPlace = me.divide(baseInteger, divisor)
    if thisPlace[1] <> 0 or resultingBaseInteger.count then --add places if the place is significant or if higher order places
      --exist
      resultingBaseInteger.add(0)
      resultingBaseInteger = me.add(resultingBaseInteger, thisPlace)
      baseInteger = me.subtract(baseInteger, me.multiply(thisPlace, divisor))
    end if
  end repeat


  if resultIsNegative then resultingBaseInteger.addAt(1, -1)
  return resultingBaseInteger
end convertBase

on absoluteValue me, baseInteger
  --copyright © 2004 Daniel W. Nelson
  if me.isNegative(baseInteger) then return me.negate(baseInteger)
  return baseInteger
end absoluteValue

on isNegative me, baseInteger
  --copyright © 2004 Daniel W. Nelson
  return baseInteger[1] < 0
end isNegative

on negate me, baseInteger
  --copyright © 2004 Daniel W. Nelson
  baseInteger = baseInteger.duplicate()
  if baseInteger[1] < 0 then
    baseInteger.deleteAt(1)
  else
    baseInteger.addAt(1, -1)
  end if
  return baseInteger
end negate

on lessThanOrEqual me, baseInteger, anotherBaseInteger
  --copyright © 2004 Daniel W. Nelson
  return not(me.greaterThan(baseInteger, anotherBaseInteger))
end lessThanOrEqual

on greaterThanOrEqual me, baseInteger, anotherBaseInteger
  --copyright © 2004 Daniel W. Nelson
  return not(me.lessThan(baseInteger, anotherBaseInteger))
end greaterThanOrEqual

on lessThan me, baseInteger, anotherBaseInteger
  --copyright © 2004 Daniel W. Nelson
  return me.greaterThan(anotherBaseInteger, baseInteger)
end lessThan

on equals me, baseInteger, anotherBaseInteger
  --copyright © 2004 Daniel W. Nelson
  return baseInteger = anotherBaseInteger
end equals

on greaterThan me, baseInteger, anotherBaseInteger
  --copyright © 2004 Daniel W. Nelson
  if baseInteger[1] < 0 and anotherBaseInteger[1] < 0 then
    return me.greaterThan(me.negate(anotherBaseInteger), me.negate(baseInteger))
  else if baseInteger[1] < 0 then
    return FALSE --the first parameter is less than zero and the second is not less than zero
  else if anotherBaseInteger[1] < 0 then
    return TRUE --the second parameter is less than zero and the first is not less than zero


  else if baseInteger.count <> anotherBaseInteger.count then --has more orders (analogous to one having
    --a hundredths place while the other only has a tens place)
    return baseInteger.count > anotherBaseInteger.count

  else --compare each order, starting with the most significant.  if they differ, return TRUE iff
    --the first parameter is larger than the second parameter
    repeat with i = 1 to baseInteger.count
      if baseInteger[i] <> anotherBaseInteger[i] then return baseInteger[i] > anotherBaseInteger[i]
    end repeat
  end if

  return FALSE
end greaterThan

on add me, baseInteger, anotherBaseInteger
  --copyright © 2004 Daniel W. Nelson
  --returns a base integer that is equal to baseInteger + anotherBaseInteger

  if baseInteger[1] < 0 and anotherBaseInteger[1] < 0 then
    baseInteger = baseInteger.duplicate()
    anotherBaseInteger = anotherBaseInteger.duplicate()
    baseInteger.deleteAt(1)
    anotherBaseInteger.deleteAt(1)
    resultIsNegative = TRUE

  else if baseInteger[1] < 0 then
    return me.subtract(anotherBaseInteger, me.negate(baseInteger))

  else if anotherBaseInteger[1] < 0 then
    return me.subtract(baseInteger, me.negate(anotherBaseInteger))

  else
    resultIsNegative = FALSE

  end if


  resultingBaseInteger = []
  carry = FALSE
  cnt = max(baseInteger.count, anotherBaseInteger.count) - 1
  repeat with i = 0 to cnt
    if i >= baseInteger.count then
      anInteger = anotherBaseInteger[anotherBaseInteger.count - i]
    else if i >= anotherBaseInteger.count then
      anInteger = baseInteger[baseInteger.count - i]
    else
      anInteger = baseInteger[baseInteger.count - i] + anotherBaseInteger[anotherBaseInteger.count - i]
    end if
    if carry then
      anInteger = anInteger + 1
      carry = FALSE
    end if
    if anInteger >= p_base then
      carry = TRUE
      anInteger = anInteger - p_base
    end if
    resultingBaseInteger.addAt(1, anInteger)
  end repeat

  if carry then resultingBaseInteger.addAt(1, 1)

  if resultIsNegative then resultingBaseInteger.addAt(1, -1)
  return me._simplifybaseInteger(resultingBaseInteger)
end add

on subtract me, baseInteger, anotherBaseInteger
  --copyright © 2004 Daniel W. Nelson
  --returns a base integer that is equal to baseInteger - anotherBaseInteger

  if baseInteger[1] < 0 and anotherBaseInteger[1] < 0 then --a negative minus a negative =>
    --a negative plus a positive. switch it around to get a positive minus a positive
    baseInteger = baseInteger.duplicate()
    anotherBaseInteger = anotherBaseInteger.duplicate()
    baseInteger.deleteAt(1)
    anotherBaseInteger.deleteAt(1)
    temp = baseInteger
    baseInteger = anotherBaseInteger
    anotherBaseInteger = temp

  else if baseInteger[1] < 0 then --negative minus a positive. simply add the two negatives
    return me.add(baseInteger, me.negate(anotherBaseInteger))

  else if anotherBaseInteger[1] < 0 then --positive minus a negative.  simply add the two positives
    return me.add(baseInteger, me.negate(anotherBaseInteger))
  end if
  --we now have a positive minus a positive
  if me.lessThan(baseInteger, anotherBaseInteger) then --the first integer is smaller than the second
    return me.negate(me.subtract(anotherBaseInteger, baseInteger))
  end if

  resultingBaseInteger = []
  inverseCarry = FALSE
  cnt = max(baseInteger.count, anotherBaseInteger.count) - 1
  repeat with i = 0 to cnt
    if i >= anotherBaseInteger.count then --we know that largerInteger has equal or more places than
      --anotherBaseInteger from the above lessThan comparison
      anInteger = baseInteger[baseInteger.count - i]
    else
      anInteger = baseInteger[baseInteger.count - i] - anotherBaseInteger[anotherBaseInteger.count - i]
    end if
    if inverseCarry then
      anInteger = anInteger - 1
      inverseCarry = FALSE
    end if
    if anInteger < 0 then
      inverseCarry = TRUE
      anInteger = anInteger + p_base
    end if
    resultingBaseInteger.addAt(1, anInteger)
  end repeat
  --no inverseCarry after this since we checked above that we were subtracting the
  --smaller from the larger (or equal from equal)

  return me._simplifybaseInteger(resultingBaseInteger)
end subtract

on multiply me, baseInteger, anotherBaseInteger
  --copyright © 2004 Daniel W. Nelson
  --baseInteger and anotherBaseInteger are base integers (defined in the makeIntegerIntoBaseNumber handler)
  --returns a base integer that is equal to baseInteger * anotherBaseInteger

  if baseInteger[1] < 0 and anotherBaseInteger[1] < 0 then
    baseInteger = baseInteger.duplicate()
    anotherBaseInteger = anotherBaseInteger.duplicate()
    baseInteger.deleteAt(1)
    anotherBaseInteger.deleteAt(1)
    resultIsNegative = FALSE

  else if baseInteger[1] < 0 then
    baseInteger = baseInteger.duplicate()
    baseInteger.deleteAt(1)
    resultIsNegative = TRUE

  else if anotherBaseInteger[1] < 0 then
    anotherBaseInteger = anotherBaseInteger.duplicate()
    anotherBaseInteger.deleteAt(1)
    resultIsNegative = TRUE

  else
    resultIsNegative = FALSE

  end if

  resultingBaseInteger = [0]
  carry = 0
  repeat with i = baseInteger.count down to 1
    tempBaseInteger = []
    repeat with k = 1 to baseInteger.count - i
      tempBaseInteger.add(0) --think of this as standard multiplication: add zeros to move the number
      --one place to the left for each time iterating through the bottom number:
      --  baseInteger
      --* anotherBaseInteger
      -- _____________________
      -- resultingBaseInteger
    end repeat
    repeat with j = anotherBaseInteger.count down to 1
      anInteger = anotherBaseInteger[j] * baseInteger[i]

      if carry then
        anInteger = anInteger + carry
        carry = 0
      end if

      if anInteger >= p_base then
        carry = anInteger / p_base
        anInteger = anInteger - carry * p_base
      end if
      tempBaseInteger.addAt(1, anInteger)
    end repeat


    if carry then
      tempBaseInteger.addAt(1, carry) --tempBaseInteger is already properly computed
      carry = 0
    end if
    resultingBaseInteger = me.add(resultingBaseInteger, tempBaseInteger)
  end repeat

  if carry then
    tempBaseInteger = []
    repeat with k = 1 to baseInteger.count - i
      tempBaseInteger.add(0) --think of this as standard multiplication: add zeros to move the number
      --one place to the left for each time iterating through the bottom number:
      --  baseInteger
      --* anotherBaseInteger
      -- _____________________
      -- resultingBaseInteger
    end repeat
    tempBaseInteger.addAt(1, carry)
    resultingBaseInteger = me.add(resultingBaseInteger, tempBaseInteger)
  end if
  if resultIsNegative then resultingBaseInteger.addAt(1, -1)
  return me._simplifybaseInteger(resultingBaseInteger)
end multiply

on divide me, numerator, denominator
  --copyright © 2004 Daniel W. Nelson
  --numerator and denominator are base integers (defined in the makeIntegerIntoBaseNumber handler)
  --returns a base integer that is equal to numerator / denominator
  numerator = numerator.duplicate() --this process is destructive to the numerator

  if numerator[1] < 0 and denominator[1] < 0 then
    denominator = denominator.duplicate()
    numerator.deleteAt(1)
    denominator.deleteAt(1)
    resultIsNegative = FALSE

  else if numerator[1] < 0 then
    numerator.deleteAt(1)
    resultIsNegative = TRUE

  else if denominator[1] < 0 then
    denominator = denominator.duplicate()
    denominator.deleteAt(1)
    resultIsNegative = TRUE

  else
    resultIsNegative = FALSE

  end if

  resultingBaseInteger = []
  remainder = 0
  repeat while numerator.count
    leftPartOfNumerator = []
    leftPartOfNumerator.add(numerator[1] + remainder)
    remainder = 0
    numerator.deleteAt(1)
    repeat while me.lessThan(leftPartOfNumerator, denominator) and numerator.count
      --find the fewest digits off the left side of the numerator that are greater than or equal to the denominator
      leftPartOfNumerator.add(numerator[1])
      numerator.deleteAt(1)
    end repeat

    if resultingBaseInteger.count then
      repeat with k = leftPartOfNumerator.count - 1 down to 1 --need to add a zero for every place we skip
        resultingBaseInteger.add(0)
      end repeat
    end if

    if me.lessThan(leftPartOfNumerator, denominator) then
      if leftPartOfNumerator.count then resultingBaseInteger.add(0) --since we aren't adding any current value below, we
      --need to add the one zero we omitted in the preceding repeat loop
      exit repeat --finished dividing
    end if

    minInt = 1
    maxInt = p_base
    repeat while TRUE --multiply by an increasing amount until the amount is greater than the fewest
      --digits off the left side of the numerator.  the place will be one less than that
      currentValue = (minInt + maxInt) / 2
      multipliedResult = me.multiply(denominator, [currentValue])
      if me.greaterThan(multipliedResult, leftPartOfNumerator) then
        if maxInt = minInt + 1 then --the max and min integers bracket the float that would be the real answer
          currentValue = currentValue - 1
          exit repeat
        end if

        maxInt = currentValue
      else if me.lessThan(multipliedResult, leftPartOfNumerator) then
        if maxInt = minInt + 1 then
          exit repeat
        end if
        minInt = currentValue
      else --equals
        exit repeat
      end if
    end repeat
    remainder =  me.subtract(leftPartOfNumerator, me.multiply(denominator, [currentValue]))[1]
    resultingBaseInteger.add(currentValue)
  end repeat

  if not(resultingBaseInteger.count) then return [0]
  if resultIsNegative then resultingBaseInteger.addAt(1, -1)
  return resultingBaseInteger
end divide

on makeIntegerIntoBaseNumber me, anInteger
  --copyright © 2004 Daniel W. Nelson
  --if positive, anInteger must be less than or equal to 2^31 - 1 (2147483647)
  --if negative, anInteger must be greater than -(2^31 - 1)
  --a base integer integer is guaranteed to have at least one list element
  baseInteger = []
  if not(anInteger) then --the integer is zero
    return [0]
  else if anInteger < 0 then
    resultIsNegative = TRUE
    anInteger = - anInteger
  else
    resultIsNegative = FALSE
  end if

  --compute the smallest power that, dividing anInteger by the p_base raised to that power gives zero with
  --integer division
  divisor = p_base
  power = 1
  repeat while anInteger / divisor <> 0
    divisor = p_base
    power = power + 1
    repeat with j = power - 1 down to 1
      divisor = divisor * p_base
    end repeat
    if divisor <= 0 then exit repeat --we have exceded the integer math for this number
  end repeat
  --end: compute the smallest power that...

  repeat with i = power down to 1
    divisor = 1
    repeat with j = i - 1 down to 1
      divisor = divisor * p_base
    end repeat
    thisPlace = anInteger / divisor
    if thisPlace or baseInteger.count then --add places if the place is significant or if higher order places
      --exist
      baseInteger.add(thisPlace)
      anInteger = anInteger - thisPlace * divisor
    end if
  end repeat

  if resultIsNegative then baseInteger.addAt(1, -1)
  return baseInteger
end makeIntegerIntoBaseNumber

on baseIntegerToInteger me, baseInteger
  --copyright © 2004 Daniel W. Nelson
  --will only work for positive integers <= 2^31 - 1 and negative integers > -(2^31 - 1)
  anInteger = 0
  if baseInteger[1] < 0 then
    baseInteger = baseInteger.duplicate()
    baseInteger.deleteAt(1)
    resultIsNegative = TRUE
  end if
  repeat with i = baseInteger.count down to 1
    multiplier = integer(power(p_base, baseInteger.count - i))
    anInteger = anInteger + baseInteger[i] * multiplier
  end repeat

  if resultIsNegative then return -anInteger
  return anInteger
end baseIntegerToInteger

on test me
  --copyright © 2004 Daniel W. Nelson

  --integers correctly mapping back and forth
  repeat with i = 1 to 100
    anInteger = 458529558 ---random(the maxInteger - 1)
    baseInteger = me.makeIntegerIntoBaseNumber(anInteger)
    anotherInteger = me.baseIntegerToInteger(baseInteger)
    if anInteger <> anotherInteger then
      put(anInteger && baseInteger && anotherInteger)
      exit repeat
    end if
  end repeat
  --end: integers correctly mapping back and forth

  --integers correctly adding
  repeat with i = 1 to 100
    anInteger = random(the maxInteger / 2 - 1)
    if random(2) = 1 then anInteger = - anInteger
    anotherInteger = random(the maxInteger / 2 - 1)
    if random(2) = 1 then anotherInteger = - anotherInteger
    --    anInteger = 980207055
    --    anotherInteger = -1001414088
    baseInteger = me.makeIntegerIntoBaseNumber(anInteger)
    anotherBaseInteger = me.makeIntegerIntoBaseNumber(anotherInteger)

    sum = anInteger + anotherInteger
    largeSum = me.add(baseInteger, anotherBaseInteger)
    anotherSum = me.baseIntegerToInteger(largeSum)

    if sum <> anotherSum then
      put(anInteger && anotherInteger && sum && anotherSum)
      exit repeat
    end if
  end repeat
  --end: integers correctly adding



  --integers correctly multiplying
  repeat with i = 1 to 100
    anInteger = random(100)
    if random(2) = 1 then anInteger = - anInteger
    anotherInteger = random(100)
    if random(2) = 1 then anotherInteger = - anotherInteger

    baseInteger = me.makeIntegerIntoBaseNumber(anInteger)
    anotherBaseInteger = me.makeIntegerIntoBaseNumber(anotherInteger)

    multiple = anInteger * anotherInteger
    largeMultiple = me.multiply(baseInteger, anotherBaseInteger)
    anotherMultiple = me.baseIntegerToInteger(largeMultiple)

    if multiple <> anotherMultiple then
      put(anInteger && anotherInteger && multiple && anotherMultiple)
      exit repeat
    end if
  end repeat
  --end: integers correctly multiplying



  --integers correctly multiplying
  repeat with i = 1 to 100
    anInteger = random(100)
    if random(2) = 1 then anInteger = - anInteger
    anotherInteger = random(100)
    if random(2) = 1 then anotherInteger = - anotherInteger

    baseInteger = me.makeIntegerIntoBaseNumber(anInteger)
    anotherBaseInteger = me.makeIntegerIntoBaseNumber(anotherInteger)

    multiple = anInteger / anotherInteger
    largeMultiple = me.divide(baseInteger, anotherBaseInteger)
    anotherMultiple = me.baseIntegerToInteger(largeMultiple)

    if multiple <> anotherMultiple then
      put(anInteger && anotherInteger && multiple && anotherMultiple)
      exit repeat
    end if
  end repeat
  --end: integers correctly dividing
end test

on _simplifybaseInteger me, baseInteger
  --copyright © 2004 Daniel W. Nelson
  --modify baseInteger so that zero is always considered positive and no leading zeros are found
  --prior to a non-zero (except for the singles digit)

  if baseInteger[1] < 0 then
    baseInteger = baseInteger.duplicate()
    baseInteger.deleteAt(1)
    resultIsNegative = TRUE
  end if

  repeat while baseInteger.count > 1 and baseInteger[1] = 0
    baseInteger.deleteAt(1)
  end repeat

  if baseInteger.count = 1 and baseInteger[1] = 0 then return [0] --keep zero as positive

  if resultIsNegative then baseInteger.addAt(1, -1)
  return baseInteger
end _simplifybaseInteger

Upload Provided by ABCUpload ASP

Contact

MMI
22 West Court Sq
Suite 2C
Newnan, GA 30263
USA

Fax - (206) 339-5833

Send e-mail