eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'LargeInteger':
Home

everywhere
www.exept.de
for:
[back]

Class: LargeInteger

Inheritance:

   Object
   |
   +--Magnitude
      |
      +--ArithmeticValue
         |
         +--Number
            |
            +--Integer
               |
               +--LargeInteger
Package:
stx:libbasic
Category:
Magnitude-Numbers
Version:
rev: 1.201 date: 2010/04/14 08:00:14
user: stefan
file: LargeInteger.st directory: libbasic
module: stx stc-classLibrary: libbasic
Author:
Claus Gittinger

Description:


This class provides arbitrary precision integers. These are represented as:
  sign (-1/0/+1) and, if sign ~~ 0
  a ByteArray of digits with 8 bits per element;
  least significant 8 bits at index 1 ...

The implementation is not completely tuned for high performance
(more key-methods should be rewritten as primitives), although the
common operations have been pretty tuned for some architectures.

LargeIntegers are usually not created explicitely, but result from
SmallInteger arithmetic (overflowing the SmallInteger range).
Also, results of LargeInteger operations are converted to back to
SmallIntegers, when possible (see #compressed).

In contrast to ST-80, there is only one class for LargeIntegers, keeping
the sign as an instance variable (ST-80 has LargePositiveInteger and
LargeNegativeInteger). This may change.

Related information:

    Number
    Float
    Fraction
    FixedPoint
    SmallInteger

Class protocol:

instance creation
o  digitBytes: aByteArrayOfDigits
create and return a new LargeInteger with digits (lsb-first)
from the argument, aByteArray.
Experimental interface - May change/be removed without notice.

o  digitBytes: aByteArrayOfDigits MSB: msb
create and return a new LargeInteger with digits (which may be in either msb/lsb order)
from the argument, aByteArray.

o  new
catch creation message.
LargeIntegers are only created by system code, which
uses basicNew and cares for correct initialization.

o  new: numberOfDigits
catch creation message

o  value: aSmallInteger
create and return a new LargeInteger with value taken from
the argument, aSmallInteger.
Notice:
this should be only used internally, since such small
largeIntegers do not normally occur in the system.
(They are used by myself)
May change/be removed without notice.

queries
o  isBuiltInClass
return true if this class is known by the run-time-system.
Here, true is returned.

Instance protocol:

arithmetic
o  * aNumber
return the product of the receiver and the argument.

o  + aNumber
return the sum of the receiver and the argument, aNumber

o  - aNumber
return the difference of the receiver and the argument, aNumber

o  / aNumber
return the quotient of the receiver and the argument, aNumber

o  // aNumber
return the quotient of the receiver and the argument, aNumber.
The result is truncated toward negative infinity and negative,
if the operands signs differ.
The following is always true:
(receiver // aNumber) * aNumber + (receiver \\ aNUmber) = receiver

o  \\ aNumber
Answer the integer remainder m defined by division with truncation toward
negative infinity. The remainder has the same sign as aNumber.
m < |aNumber| AND there is an integer k with (k * aNumber + m) = self
The following is always true:
(receiver // aNumber) * aNumber + (receiver \\ aNumber) = receiver
Compare with #rem:

o  abs
return my absolute value. redefined for speed.

o  divMod: aNumber
return an array filled with self // aNumber and
self \\ aNumber.
The result is only defined for positive receiver and
argument.

o  negated
return an integer with value negated from the receivers value.

o  quo: aNumber
return the quotient of the receiver and the argument, aNumber.
The result is truncated toward zero (which is different from //, which
truncates toward negative infinity).
The results sign is negative if the receiver has a sign
different from the args sign.
The following is always true:
(receiver quo: aNumber) * aNumber + (receiver rem: aNumber) = receiver

o  rem: aNumber
return the remainder of division of the receiver by the argument, aNumber.
The returned remainder has the same sign as the receiver.
The following is always true:
(receiver quo: aNumber) * aNumber + (receiver rem: aNumber) = receiver

bit operators
o  bitAnd: anInteger
return the bitwise-and of the receiver and the argument, anInteger

o  bitAt: anIntegerIndex
return the value of the index's bit (index starts at 1) as 0 or 1.
Notice: the result of bitAt: on negative receivers is not
defined in the language standard (since the implementation
is free to choose any internal representation for integers)

o  bitXor: anInteger
return the bitwise-or of the receiver and the argument, anInteger.
Here, a specially tuned version for largeInteger arguments
(to speed up some cryptographic code)

o  lowBit
return the bitIndex of the lowest bit set. The returned bitIndex
starts at 1 for the least significant bit.
Returns 0 if no bit is set.
For negative numbers, the low bit of my absolute value is returned.
Redefined here for more performance of the gcd: algorithm, which
is used when big fractions are reduced (should we write a primitive for this ?).

o  setBit: index
return a new integer, where the specified bit is on.
Bits are counted from 1 starting with the least significant.
The methods name may be missleading: the receiver is not changed,
but a new number is returned. Should be named #withBitSet:

bit operators-32bit
o  bitInvert32
return the value of the receiver with all bits inverted in 32bit signed int space
(changes the sign)

o  bitRotate32: shiftCount
return the value of the receiver rotated by shiftCount bits,
but only within 32 bits, rotating left for positive, right for negative counts.
Rotates through the sign bit.
Useful for crypt algorithms, or to emulate C/Java semantics.

o  bitShift32: shiftCount
return the value of the receiver shifted by shiftCount bits,
but only within 32 bits, shifting into/out-of the sign bit.
May be useful for communication interfaces, to create ST-numbers
from a signed 32bit int value given as individual bytes,
or to emulate C/Java semantics.
The shift is unsigned

o  bitXor32: aNumber
return the xor of the receiver and the argument.
The argument must be a SmallInteger or a 4-byte LargeInteger.
If the result overflows the 32 bit range, the value modulo 16rFFFFFFFF is returned.
This is of course not always correct, but allows for C/Java behavior to be emulated.

byte access
o  digitAt: index
return 8 bits of value, starting at byte index

o  digitAt: index put: aByte
set the 8 bits, index is a byte index

o  digitByteAt: index
return 8 bits of my signed value, starting at byte index.
For positive receivers, this is the same as #digitAt:;
for negative ones, the actual bit representation is returned.

o  digitBytes
return a byteArray filled with the receivers bits
(8 bits of the absolute value per element).
Least significant byte is first!

o  digitBytesMSB: msbFlag
return a byteArray filled with the receivers bits
(8 bits of the absolute value per element),
if msbflag = true, most significant byte is first,
otherwise least significant byte is first

o  digitLength
return the number bytes used by this Integer.
For negative receivers, the digitLength of its absolute value
is returned.

o  digits
obsolete, use #digitBytes

** This is an obsolete interface - do not use it (it may vanish in future versions) **

coercing & converting
o  asLargeInteger
return a LargeInteger with same value as myself - thats me

o  asSigned32
return a 32-bit integer with my bit-pattern. Receiver must be unsigned (i.e. positive).
May be required for bit operations on the sign-bit and/or to
convert C/Java numbers.

o  asSmallInteger
return a SmallInteger with same value as myself -
the result is invalid if the receivers value cannot
be represented as a SmallInteger.
Q: should we raise an exception if this happens ?

o  asUnsigned32
return a 32-bit integer with my bit-pattern. Receiver must be unsigned (i.e. positive).
May be required for bit operations on the sign-bit and/or to
convert C/Java numbers.

o  coerce: aNumber
convert the argument aNumber into an instance of the receivers class and return it.

o  compressed
if the receiver can be represented as a SmallInteger, return
a SmallInteger with my value;
otherwise remove leading zero bytes in the digitByte array
and return the receiver

o  generality
return the generality value - see ArithmeticValue>>retry:coercing:

o  value: aSmallInteger
setup my contents to represent the same value as aSmallInteger.
This method will fail, if the argument is not a smallInteger.
This should only be used internally,
since it will create an unnormalized LargeInt (by purpose) if asked for.

comparing
o  < aNumber
return true, if the argument, aNumber is greater than the receiver

o  = aNumber
return true, if the argument represents the same numeric value
as the receiver, false otherwise

o  > aNumber
return true, if the argument, aNumber is less than the receiver

o  hash
return an integer useful for hashing on large numbers

double dispatching
o  differenceFromInteger: anInteger
sent, when anInteger does not know how to subtract the receiver.
Return the result of 'anInteger - self'. The argument must be a SmallInteger.

o  equalFromInteger: anInteger
sent when an integer does not know how to compare to the receiver, a largeInt

o  lessFromInteger: anInteger
sent when an integer does not know how to compare to the receiver, a largeInt

o  productFromInteger: anInteger
sent, when anInteger does not know how to multiply the receiver.
Return the product of the receiver and the argument, aSmallInteger

o  sumFromInteger: anInteger
sent, when anInteger does not know how to add the receiver.
Return the sum of the receiver and the argument, (which must be a SmallInteger)

modulu arithmetic
o  plus32: aNumber
return the sum of the receiver and the argument, as SmallInteger.
The argument must be another SmallInteger.
If the result overflows the 32 bit range, the value modulo 16rFFFFFFFF is returned.
This is of course not always correct, but allows for C/Java behavior to be emulated.

printing & storing
o  xxxstoreOn: aStream
append a representation of the receiver to aStream, which can
be used to reconstruct the receiver.

private
o  absDivMod: anInteger
return an array with two LargeIntegers representing
abs(self) // abs(theArgument) and abs(self) \\ abs(theArgument).
Used as a helper for \\, //, rem: and quo:.
This method needs a rewrite.

o  absEq: aLargeInteger
return true, if abs(self) = abs(theArgument)

o  absFastDivMod: aPositiveSmallInteger
return an array with two LargeIntegers representing
abs(self) // aPositiveSmallInteger and
abs(self) \\ aPositiveSmallInteger.

o  absFastMinus: aSmallInteger sign: newSign
return a LargeInteger representing abs(self) - abs(theArgument)
with sign: newSign.
The result is normalized.
This is a helper for addition and subtraction - not for public use.

o  absFastPlus: aSmallInteger sign: newSign
return a LargeInteger representing abs(self) + abs(theArgument).
with sign: newSign.
The result is normalized. The argument must be a smallInteger
with byteSize one less than the integer byteSize.
This is a helper for addition and subtraction - not for public use.

o  absLess: aLargeInteger
return true, if abs(self) < abs(theArgument).
This handles unnormalized largeIntegers.

o  absLessEq: aLargeInteger
return true, if abs(self) <= abs(theArgument).
This handles unnormalized largeIntegers.

o  absMinus: aLargeInteger sign: newSign
return a LargeInteger representing abs(self) - abs(theArgument)
with sign: newSign.
The result is normalized. The argument must be a largeInteger
with a byteSize smaller than the receivers byteSize.
This is a helper for addition and subtraction - not for public use.

o  absMod: anInteger
return a LargeIntegers representing
abs(self) \\ abs(theArgument).
Used as a helper for \\ and rem:

o  absMul: aLargeInteger
return a LargeInteger representing abs(self) * abs(theArgument)

o  absPlus: aLargeInteger sign: newSign
return a LargeInteger representing abs(self) + abs(theArgument)
with sign: newSign.
The result is normalized. The argument must be a smallInteger
with byteSize one less than the integer byteSize.
This is a helper for addition and subtraction - not for public use.

o  absSubtract: aLargeInteger
private helper for division:
destructively subtract aLargeInteger from myself
AND return true, if the result is non-zero, false otherwise.
(i.e. this method has both a return value and a side-effect
on the receiver)
Only allowed for positive receiver and argument
The receiver must be >= the argument.
The receiver must be a temporary scratch-number

o  div2
private helper for division:
destructively divide the receiver by 2.

o  mul2
private helper for division:
destructively multiply the receiver by 2.

o  mul256
private helper for division:
destructively multiply the receiver by 256.

o  numberOfDigits: nDigits
digitByteArray := ByteArray uninitializedNew:nDigits.

o  setDigits: digits

o  sign: aNumber

testing
o  even
return true if the receiver is even

o  negative
return true, if the receiver is < 0

o  odd
return true if the receiver is odd

o  positive
return true, if the receiver is >= 0

o  sign
return the sign of the receiver (-1, 0 or 1)

o  strictlyPositive
return true, if the receiver is > 0

ST/X 6.1.1; WebServer 1.620 at exept:8081; Wed, 23 May 2012 19:54:13 GMT