by Roger K.W. Hui

[Published in Vector Vol.13 No.2. The display of extended integers is that used in J4.]

J3.02, released in June 1996, provides extended integers; the facilities are similar to
those described in the recent series of Vector articles by Sullivan [1995, 1996].
The monad
`x:`

applies to integers and produces extended precision integers.
Extended constants may also be entered as a sequence of decimal digits terminated by an x,
for example, the 2-element vector
`1234x 56x`

is equivalent to
`x: 1234 56`

. Various primitives produce extended results if the argument(s) are extended. For example:

! 40 8.15915e47 ! 40x 815915283247897734345611269596115894272000000000 */ x: >: i. 40 815915283247897734345611269596115894272000000000

Some verbs v signal domain error on some extended arguments because the result is not integral;
however,
`<.@v`

and
`>.@v`

are closed on extended arguments. For example:

1234 % 5x |domain error | 1234 %5x 1234 <.@% 5x 246 1234 % 2x 617 1234 >.@% 2x 617 ] r=. <.@%: 2 * 10^50x 14142135623730950488016887 *: r + ,. _1 0 1 199999999999999999999999964868192079803881021136996 199999999999999999999999993152463327265781997170769 200000000000000000000000021436734574727682973204544

Verbs which have not been extended but will be extended, signal nonce error on extended arguments
(for example, the monad
`<.@o.`

, the floor of times); verbs which have not been extended
and will not be extended (for example
`%.`

, matrix inverse and matrix divide), signal
domain error on extended arguments.
Comparisons involving extended integers are exact.
Various non-integer values can be computed to a large number of decimal places using extended integers.
For example, the golden ratio phi can be computed to 40 decimal places using several different methods:

Method 1. Phi is
`-:1+%:5`

, half of one plus the square root of 5.

-: 1 + %: 5 1.61803 <.@-: s + <.@%: 5 * *: s=. 10^40x 16180339887498948482045868343656381177203

Method 2. Phi is the limit of the continued fraction
`(+%)/n$1`

.

(+%)/20$1 1.61803

Pairs of integers are used to represent fractions. The number of terms required can be estimated using ordinary (non-extended) operations. Thus:

reduce=: % +./ plus =: [: reduce +/@(*|.) , *&{: recip =: |. reduce 10 25x Reduce to lowest terms 2 5 3 4x plus 5 6x Sum in lowest terms 19 12 recip 3 4x Reciprocal 4 3 (plus recip)/ 20$1x 20 terms of continued fraction 6765 4181 x=. (+%)/\ 20$1 Now estimate # of terms req'd (-:1+%:5) - x Approximation errors 0.618034 _0.381966 0.118034 _0.04863268 0.01803399 ... 2 %/\ (-:1+%:5) - x Ratios in approximation errors _1.61803 _3.23607 _2.42705 _2.69672 _2.58885 _2.62931 ... _5[\ 2 %/\ (-:1+%:5) - x Present in 5 columns _1.61803 _3.23607 _2.42705 _2.69672 _2.58885 _2.62931 _2.61375 _2.61967 _2.61741 _2.61827 _2.61794 _2.61807 _2.61802 _2.61804 _2.61803 _2.61803 _2.61803 _2.61803 _2.61803 0 2.6 ^. 10^40 About 96 terms are required 96.3917 y=. (plus recip)/\ 100 2$1x $y 100 2 ,. <.@%/"1 (95)}. (10^40x 0) *"1 y 16180339887498948482045868343656381177204 16180339887498948482045868343656381177202 16180339887498948482045868343656381177203 16180339887498948482045868343656381177202 16180339887498948482045868343656381177203

Method 3. Using the verbs previously defined to work on integer pairs representing fractions, we have:

(plus recip)/\ 10 2$1x 1 1 2 1 3 2 5 3 8 5 13 8 21 13 34 21 55 34 89 55

It is seen (and easily proved) that partial sums of the continued fraction are ratios of
consecutive Fibonacci numbers. Fibonacci numbers are rows of the powers of the
matrix
`0 1,:1 1`

, computed efficiently by repeated squaring.
(See Hui [1996], "Linear Recurrences and Matrix Powers".) Thus:

x =: +/ .* Matrix product pow=: 4 : 'x/ x~^:(b#i.-#b=.#:y.) x.' ] M=: x: 0 1,:1 1 0 1 1 1 M pow 4 2 3 3 5 M x M x M x M 2 3 3 5 M pow 100 218922995834555169026 354224848179261915075 354224848179261915075 573147844013817084101 <.@% / (10^40x 0) * |. {: M pow 100 16180339887498948482045868343656381177203x

Finally, the phrase m&|@^ is supported by special code, on extended integer arguments and ordinary integer arguments alike, making it possible to compute the final result even when the intermediate result is enormous. For example:

1e6 | 2 ^ 24 777216 2 (1e6&|@^) 24 777216 2 (1e6&|@^) 10^100x 109376

Sullivan, John, Multi-Precision Arithmetic: Parts I-IV, Vector, Volume 12, 1-4, 1995 7 and 10, 1996 1 and 4.