class INTI < $IS_LT{INTI}, $STR, $HASH |
---|
**** | Implementation of arbitrary large integers. An integer x is represented by n digits to a base B:
___x_=_sign_*_(x[n-1]*B^(n-1)_+_x[n-2]*B^(n-2)_+_..._+_x[1]*B_+_x[0]) The n digits x[i] of x are hold in an array with asize >= n. The sign and n are encoded in a private feature len, with the following semantics: ___n_=_|len|,_sign_=_sign(len) and the value 0 is represented by len = 0 The operations div (/) and mod (%) obey the following rules (euclidean definition): ___x_=_(x/y)*y_+_x%y___and___0_<=_x%y_<_|y| All (non-private) methods are non-destructive, i.e. they do not modify their arguments. Thus, INTI behaves like a immutable class. Author: Robert Griesemer (gri@icsi.berkeley.edu) |
$HASH | $IS_EQ | $STR | $IS_LT{_} | AREF{_} |
abs: SAME |
---|
aclear .. Included as aclear |
---|
**** | Set each element of self to nil. Built-in. |
acopy(beg,num,srcbeg:INT, src:SAME) .. Included as acopy |
---|
**** | Copy `num' elements from `src' to self starting at index `beg' of self and index `srcbeg' of `src'. Built-in. |
acopy(beg,num:INT, src:SAME) .. Included as acopy |
---|
**** | Copy `num' elements from `src' to self starting at index `beg' of self. |
acopy(beg:INT, src:SAME) .. Included as acopy |
---|
**** | Copy as many elements from `src' to self as will fit when starting at index `beg' of self. |
acopy(src:SAME) .. Included as acopy |
---|
**** | Copy as many elements from `src' to self as will fit. Built-in. |
aget(ind:INT):T .. Included as aget |
---|
**** | The element of self with index `ind'. Built-in. |
array_ptr:C_PTR .. Included as array_ptr |
---|
aset(ind:INT, val:T) .. Included as aset |
---|
**** | Set the element of self with index `ind' to `val'. Built-in. |
asize:INT .. Included as asize |
---|
**** | The number of elements in self. Classes which inherit this may replace this by a constant to get constant sized objects (and the compiler may optimize certain operations in this case). Built-in. |
at_least(x:SAME):SAME |
---|
**** | Same as `max(x)'. |
at_most(x:SAME):SAME |
---|
**** | Same as `min(x)'. |
band(a:SAME):SAME |
---|
bcount:INT |
---|
beqv(a:SAME):SAME |
---|
bit(a:INT):BOOL |
---|
bnand(a:SAME):SAME |
---|
bnor(a:SAME):SAME |
---|
bnot:SAME |
---|
boole(a:SAME,b:INT):SAME |
---|
bor(a:SAME):SAME |
---|
bxor(a:SAME):SAME |
---|
cmp (y: SAME): INT |
---|
**** | Returns a value with the property x rel y = (x.cmp(y) rel 0), where rel stands for one of the relations =, /=, <, <=, > or >=.
|
create(f:FLT):SAME |
---|
**** | Would be much faster if INTI had set_bit. |
create(f:FLTD):SAME |
---|
**** | Would be much faster if INTI had set_bit. |
create (s: FSTR): SAME |
---|
create (s: FSTR, i: INT): SAME |
---|
**** | Creates an INTI of its decimal string representation in s starting at index i. Returns 0i if no integer is found in s. Syntax: [['+' | '-'] {digit}] |
create (x: INT): SAME |
---|
**** | Creates an INTI from x |
create(x:INTI):SAME |
---|
create (s: STR): SAME |
---|
create (s: STR, i: INT): SAME |
---|
**** | Creates an INTI of its decimal string representation in s starting at index i. Returns 0i if no integer is found in s. Syntax: [['+' | '-'] {digit}]
|
create:SAME |
---|
cube: SAME |
---|
div (y: SAME): SAME |
---|
evenly_divides(i:SAME):BOOL |
---|
**** | True if self evenly divides `i'. |
exp10: SAME |
---|
**** | 10^self |
exp2: SAME |
---|
**** | 2^self self is INTI because of conflict with INT::exp2:INT |
extended_gcd(i:SAME, out self_factor, out i_factor: SAME): SAME |
---|
**** | The three parts of the return value `g', `g1', and `g2' are such that `g' is the greatest common divisor of self and `i' and `g1*self+g2*i=g'. Uses the extended Euclidean algorithm. Geddes, et. al. p. 36. |
factorial: SAME |
---|
flt: FLT |
---|
fltd: FLTD |
---|
gcd(i:SAME):SAME |
---|
**** | The greatest common divisor of self and `i'. The result is non-negative and `x.gcd(0)=x.abs'. Uses Euclidean algorithm. Geddes, et. al. p. 34. |
hash:INT |
---|
high_bits(a:INT):SAME |
---|
highest_bit:INT |
---|
int: INT |
---|
inti: INTI |
---|
is_between(l,u:SAME):BOOL |
---|
**** | True if self between l and u. |
is_eq(y: SAME): BOOL |
---|
is_eq(arg: $OB): BOOL .. Included as is_eq |
---|
is_even: BOOL |
---|
is_exp2:BOOL |
---|
is_lt (y: SAME): BOOL |
---|
is_neg: BOOL |
---|
is_non_neg: BOOL |
---|
is_non_pos: BOOL |
---|
is_non_zero: BOOL |
---|
is_odd: BOOL |
---|
is_pos: BOOL |
---|
is_prime:BOOL |
---|
**** | True if self is a prime number. Replace by a faster algorithm. |
is_relatively_prime_to(i:SAME):BOOL |
---|
**** | True if self is relatively prime to `i'. |
is_within(tolerance,val:SAME):BOOL |
---|
is_zero: BOOL |
---|
lcm(i:SAME):SAME |
---|
**** | The least common multiple of self and `i'. Geddes, et. al. p. 28. |
log2: INT |
---|
**** | Returns the largest n with 2^n <= self for self > 0 (logarithmus dualis).
|
low_bits(a:INT):SAME |
---|
lowest_bit:INT |
---|
lrotate(a:INT):SAME |
---|
lshift(a:INT):SAME |
---|
max (y: SAME): SAME |
---|
min (y: SAME): SAME |
---|
minus (y: SAME): SAME |
---|
mod (y: SAME): SAME |
---|
negate: SAME |
---|
next_exp2:SAME |
---|
next_multiple_of(i:SAME):SAME |
---|
**** | The smallest value greater than or equal to self which is a multiple of `i'. |
plus (y: SAME): SAME |
---|
pow (i: INT): SAME |
---|
**** | Returns self raised to the power i. Returns 1 for i < 0.
|
pow (j: SAME): SAME |
---|
**** | Returns self raised to the power i. Returns 1 for i < 0.
|
rrotate(a:INT):SAME |
---|
rshift(a:INT):SAME |
---|
set_bit(a:INT):SAME |
---|
set_bit(a:INT,c:BOOL):SAME |
---|
sign: INT |
---|
sqrt: SAME |
---|
**** | square root of self. Iteration algorithm: x[0]:=self; x[n+1]:=(x+a/x)/2 We stop when the value is constant or oscillating. A routine "INTI::div(INT):INTI" could speed this up. |
square: SAME |
---|
str: STR |
---|
**** | A decimal string version of self. |
str_in (s: FSTR): FSTR |
---|
**** | Append a decimal string version of self to s and return s.
|
str_in (s: FSTR, n, b: INT, f: CHAR): FSTR |
---|
**** | Append a string representation of self to s using at least n digits to the base b and return s. If less then n digits are used for the representation of self (including its sign), the remaining left_most positions are filled with character f.
|
times (y: SAME): SAME |
---|
unset_bit(a:INT):SAME |
---|
urshift(a:INT):SAME |
---|
aelt!(once beg:INT):T .. Included as aelt! |
---|
**** | Yield each element of self starting at `beg'. Built-in. |
aelt!(once beg,once num:INT):T .. Included as aelt! |
---|
**** | Yield `num' successive elements of self starting at index `beg'. Built-in. |
aelt!(once beg,once num,once step:INT):T .. Included as aelt! |
---|
**** | Yield `num' elements of self starting at `beg' and stepping by `step' which must not be zero. Built-in. |
aelt!:T .. Included as aelt! |
---|
**** | Yield each element of self in order. Built-in. |
aind!:INT .. Included as aind! |
---|
**** | Yield the indices of self in order. |
aset!(val:T) .. Included as aset! |
---|
**** | Set successive elements of self to the values `val'. Built-in. |
aset!(once beg:INT,val:T) .. Included as aset! |
---|
**** | Set successive elements of self starting at `beg' to the values `val'. |
aset!(once beg,once num:INT,val:T) .. Included as aset! |
---|
**** | Set `num' successive elements of self starting at `beg' to the values `val'. |
aset!(once beg,once num,once step:INT, val:T) .. Included as aset! |
---|
**** | Set `num' elements of self starting at `beg' stepping by `step' to the values `val'. `step' must not be zero. |
downto!(once i:SAME):SAME |
---|
**** | Yield successive integers from self down to `i' inclusive. |
for!(once i:SAME):SAME |
---|
**** | Yields `i' successive integers starting with self. |
product!(i:SAME):SAME |
---|
**** | Yields the product of all previous values of `i'. |
step!(once num,once step:SAME):SAME |
---|
**** | Yield `num' integers starting with self and stepping by `step'. |
sum!(i:SAME):SAME |
---|
**** | Yields the sum of all previous values of `i'. |
times! |
---|
**** | Yields self times without returning anything. |
times!:SAME |
---|
**** | Yield successive integers from 0 up to self-1. |
up!:SAME |
---|
**** | Yield successive integers from self up. |
upto!(once i:SAME):SAME |
---|
**** | Yield successive integers from self to `i' inclusive. |
const B := 2 ^ log2B; |
---|
**** | binary base |
const D := 10 ^ log10D; |
---|
**** | decimal base; D <= B must hold |
append_int (s: FSTR, x, n: INT): FSTR |
---|
**** | Append a decimal version of x to s using at most n digits (filled up with 0's) and return s.
|
shared buf: FSTR; |
---|
**** | Buffer for string output. |
shared buf: FSTR; |
---|
**** | Buffer for string output. |
copy: SAME |
---|
get_u_div (x, y, q: SAME): SAME |
---|
get_u_mod (x, y, q: SAME): SAME |
---|
is_legal_aelts_arg( beg, num, step:INT) :BOOL .. Included as is_legal_aelts_arg |
---|
**** | True if the arguments are legal values for `aelts'. |
attr len: INT; |
---|
attr len: INT; |
---|
const log10D := 4; |
---|
**** |
const log2B := 15; |
---|
mul (a, b: INT): SAME |
---|
u_cmp (x, y: SAME): INT |
---|
u_div_mod (x, y: SAME): SAME |
---|
u_minus (x, y: SAME): SAME |
---|
u_mod (x: SAME, d: INT): INT |
---|
**** | e (1 <= d) and (d < B) is -- x /= 0; x will be modified |
u_plus (x, y: SAME): SAME |
---|
u_times (x, y: SAME): SAME |
---|
u_times_plus (x: SAME, y, c: INT): SAME |
---|