1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768 |
- #!/usr/bin/ruby
- # Author: Trizen
- # Date: 01 May 2022
- # https://github.com/trizen
- # Compress a number into a polynomial expression in a given base.
- func number2expr(n, base=10) {
- if (!n.is_int && n.is_rat) { # rational support
- var (nu, de) = n.nude
- return (__FUNC__(nu, base) / __FUNC__(de, base))
- }
- var D = n.digits(base).flip
- var t = D.len
- D.run_length.sum_2d {|d,l|
- t -= l
- (l == 1) ? d*Poly(t) : (((Poly(l) - 1)/(base-1) * d) * Poly(t))
- }
- }
- func number2expr_alt(n, base=10) { # returns: n * (base-1)
- if (!n.is_int && n.is_rat) { # rational support
- var (nu, de) = n.nude
- return (__FUNC__(nu, base) / __FUNC__(de, base) * (base-1))
- }
- var D = n.digits(base).flip
- var t = D.len
- D.run_length.sum_2d {|d,l|
- t -= l
- ((Poly(l) - 1) * d) * Poly(t)
- }
- }
- var tests = [
- [0b100000100000111111101, 2],
- [(7**911 - 4*(7**455) - 1), 7],
- [11113338888999999999, 10],
- [43/97, 10],
- ]
- for n,b in (tests) {
- say ("base #{'%2d'%b}: ", number2expr(n,b).pretty)
- say ("base #{'%2d'%b}: (", number2expr_alt(n,b).pretty, ")/#{b-1}")
- say ''
- assert_eq(number2expr(n,b) -> eval(b), n)
- assert_eq(number2expr_alt(n,b)/(b-1) -> eval(b), n)
- }
- __END__
- base 2: x^20 + x^14 + x^9 - x^2 + 1
- base 2: (x^21 - x^20 + x^15 - x^14 + x^9 - x^2 + x - 1)/1
- base 7: x^911 - x^456 + 3*x^455 - 1
- base 7: (6*x^911 - 4*x^456 + 4*x^455 - 6)/6
- base 10: 1/9*x^20 + 2/9*x^16 + 5/9*x^13 + 1/9*x^9 - 1
- base 10: (x^20 + 2*x^16 + 5*x^13 + x^9 - 9)/9
- base 10: (4*x + 3)/(9*x + 7)
- base 10: ((36*x^2 - 9*x - 27)/(9*x^2 - 2*x - 7))/9
|