| 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_geq (y: SAME): BOOL |
|---|
| is_gt (y: SAME): BOOL |
|---|
| is_leq (y: SAME): BOOL |
|---|
| is_lt (y: SAME): BOOL |
|---|
| is_neg: BOOL |
|---|
| is_neq(y: SAME): 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 |
|---|