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 |
---|
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_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 |
---|
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 |
---|
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 |
---|