Extended Integers in J
Vector 13:2, page 154
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 154
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
815915283247897734345611269596115894272000000000x
*/ x: >: i. 40
815915283247897734345611269596115894272000000000x
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
246x
1234 % 2x
617x
1234 >.@% 2x
617x
] r=. <.@%: 2 * 10^50x
14142135623730950488016887x
*: r + ,. _1 0 1
199999999999999999999999964868192079803881021136996x
199999999999999999999999993152463327265781997170769x
200000000000000000000000021436734574727682973204544x
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.
Method 2. Phi is the limit of the continued fraction (+%)/n$1.
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
2x 5x
3 4x plus 5 6x Sum in lowest terms
19x 12x
recip 3 4x Reciprocal
4x 3x
(plus recip)/ 20$1x 20 terms of continued fraction
6765x 4181x
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
16180339887498948482045868343656381177204x
16180339887498948482045868343656381177202x
16180339887498948482045868343656381177203x
16180339887498948482045868343656381177202x
16180339887498948482045868343656381177203x
Method 3. Using the verbs previously defined to work on integer pairs representing fractions, we have:
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
0x 1x
1x 1x
M pow 4
2x 3x
3x 5x
M x M x M x M
2x 3x
3x 5x
M pow 100
218922995834555169026x 354224848179261915075x
354224848179261915075x 573147844013817084101x
<.@% / (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:
References¶
Hui, Roger K.W., Linear Recurrences and Matrix Powers, Vector, Volume 12, Number 4, 1996 4.
Sullivan, John, Multi-Precision Arithmetic: Parts I-IV, Vector, Volume 12, 1-4, 1995 7 and 10, 1996 1 and 4.