123456789101112131415161718192021222324252627282930313233343536373839404142 |
- #!/usr/bin/ruby
- # Subquadratic algorithm for computing the sum of digits of a given integer in a given base.
- # Based on the FastIntegerOutput algorithm presented in the book:
- #
- # Modern Computer Arithmetic
- # - by Richard P. Brent and Paul Zimmermann
- #
- func FastSumOfDigits(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
- }
- var (Q,R) = A.divmod(B**k)
- var t = (k+1)>>1
- __FUNC__(R, t) + __FUNC__(Q, t)
- }(A, k)
- }
- for B in (2..100) { # run some tests
- var N = 1e20.irand
- var a = N.sumdigits(B)
- var b = FastSumOfDigits(N, B)
- assert_eq(a, b)
- }
- say FastSumOfDigits(5040, 10) #=> 9
- say FastSumOfDigits(5040, 11) #=> 20
- say FastSumOfDigits(5040, 12) #=> 13
- say FastSumOfDigits(5040, 13) #=> 24
|