Essays/Roll on BIGINTs
< Essays
Jump to navigation
Jump to search
We compute ?y where y is an extended precision integer, using existing facilities. The algorithm is to compute z=.?y1 repeatedly where y1 is a little bigger than y , until z is less than y . (The same y1 is used for a given y .) The analogy is this: We generate randomly 0 or 1 using a coin that sometimes lands on its edge, but is otherwise fair regarding head or tail. So the procedure is: flip the coin, if it lands on its edge, flip the coin again; otherwise return 0 (head) or 1 (tail).
B=: 10000x NB. base for extended precision integers vecarg=: 3 : 0 NB. vector argument for ordinary roll m=. <.10^.B NB. # digits in base d=. ":y k=. m-m|-#d NB. # decimal digits in leading digit c=.(".k{.d)++./'0'~:k}.d NB. possible leading digit (1=c)}.c,(m%~k-~#d)#B NB. c,B,...,B (if 1~:c) or B,...,B (if 1=c) ) roll=: 3 : 0 v=. vecarg y whilst. y<:z do. z=. B#.?v end. )
For example:
11^20x 672749994932560009201 roll 11^20x 593109945409601188679 roll 11^20x 395743572184338658928 roll 11^20x 252440334932881697997
The number B#.B|vecarg y is the y1 referred to above. For example:
vecarg 11^20x 7 10000 10000 10000 10000 10000 vecarg 10^4x 10000 vecarg 10^5x 10 10000 vecarg 10^6x 100 10000 vecarg 10^7x 1000 10000 vecarg 10^8x 10000 10000 vecarg 10000x 10000 vecarg 10001x 2 10000 vecarg 1234x 1234
Contributed by Roger Hui.