1234567891011121314151617181920 |
- #!/usr/bin/ruby
- # Generic implementation of the Binary Exponentiation algorithm.
- # See also:
- # https://en.wikipedia.org/wiki/Exponentiation_by_squaring
- func binary_exp(r,x,n,f) {
- for bit in (n.as_bin.flip.chars) {
- r = f(x, r) if bit
- x = f(x, x)
- }
- return r
- }
- say binary_exp(1, 3, 42, {|a,b| a * b }) # 3^42
- say binary_exp(0, 3, 42, {|a,b| a + b }) # 3*42
|