12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152 |
- #!/usr/bin/ruby
- # Subquadratic algorithm for converting a given integer into a list of digits in a given base.
- # Algorithm presented in the book:
- #
- # Modern Computer Arithmetic
- # - by Richard P. Brent and Paul Zimmermann
- #
- func FastIntegerOutput(A, B) {
- # Find k such that B^(2k - 2) <= A < B^(2k)
- var k = (A.ilog(B)>>1 + 1)
- func (A,k) {
- if (A < B) {
- return [A]
- }
- if (B**(2*(k-1)) > A) {
- --k
- }
- #assert(B**(2*k - 2) <= A, [B,k, "#{B**(2*k - 2)} <= #{A}"])
- #assert(A < B**(2*k), [B,k, "#{A} < #{B**(2*k)}"])
- var (Q,R) = A.divmod(B**k)
- var t = (k+1)>>1
- var r = __FUNC__(R, t)
- var l = __FUNC__(Q, t)
- [l..., (k - r.len).of(0)..., r...]
- }(A,k)
- }
- say FastIntegerOutput(5040, 10) #=> [5, 0, 4, 0]
- say FastIntegerOutput(5040, 11) #=> [3, 8, 7, 2]
- say FastIntegerOutput(5040, 12) #=> [2, 11, 0, 0]
- say FastIntegerOutput(5040, 13) #=> [2, 3, 10, 9]
- for B in (2..100) { # run some tests
- var N = 1e20.irand
- var a = N.digits(B)
- var b = FastIntegerOutput(N, B)
- assert_eq(a.flip, b)
- }
|