Essays/Roll on BIGINTs

From J Wiki
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:


   roll 11^20x
   roll 11^20x
   roll 11^20x

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
   vecarg 10^5x
10 10000
   vecarg 10^6x
100 10000
   vecarg 10^7x
1000 10000
   vecarg 10^8x
10000 10000

   vecarg 10000x
   vecarg 10001x
2 10000
   vecarg 1234x

Contributed by Roger Hui.