3

Is there any way to implement the Uint256 -> Uint256 function f(x) = floor(1.01 ^ x), using only a constant number of operations add, mul, sub, div, exp, all of those can only operate on integer numbers?

MaiaVictor
  • 51,090
  • 44
  • 144
  • 286
  • 1
    But what do you want to do about the floating point component of the output, if there is one (quite likely)? I think an ALU is basically what a computer would use to compute an exponent, so this is a known problem. – Tim Biegeleisen Dec 01 '16 at 01:55
  • @TimBiegeleisen floor it out (I edited the OP). Makes sense that this is a known problem, I'd appreciate some reference. – MaiaVictor Dec 01 '16 at 01:57
  • Not sure I see how that helps, that algorithm seems to use floats... – MaiaVictor Dec 01 '16 at 02:01
  • 1
    I upvoted your question, I hope you get the answer you're looking for. – Tim Biegeleisen Dec 01 '16 at 02:04
  • @TimBiegeleisen thank you! – MaiaVictor Dec 01 '16 at 02:04
  • Squaring could still work by using `101` as the base and reducing the intermediate results by factors of 100 any time they get too large. The trick would be to balance this so that no precision is lost in the last digits. – Lutz Lehmann Dec 01 '16 at 02:13
  • 2
    Do you have to be able to handle the whole int256 range without overflowing i.e. if the result can fit in a int256 then you must be able to calculate it using only these operations and only using int256 variables? FWIW, a lookup table for this would need 17833 entries – samgak Dec 01 '16 at 05:00
  • 2
    Stupid question: is `Int256` the type that takes values in `[0..255]`, or the type that uses 256 bits to represent an integer? Or something else? – AakashM Dec 01 '16 at 08:41
  • 1
    and also it is signed or not? and standard two's complement in case of yes? In case of 256 bits I see no point of not using loops unless you want to implement this directly with silicon instead of program – Spektre Dec 01 '16 at 08:58
  • @AakashM 256 bits! – MaiaVictor Dec 01 '16 at 17:42
  • @Spektre not signed!! actually. Point of not using loops is that I need to run it in a VM which charges real money for each executed arithmetic operation. – MaiaVictor Dec 01 '16 at 17:42
  • @samgak I think it is OK if it works for just `Uint64` (or perhaps smaller if that is still too big) inputs/outputs since I won't be using more than that. It is able to use `Uint256` numbers in intermediate computations, as that is the native word size. – MaiaVictor Dec 01 '16 at 17:45
  • What is `exp`? It can't be the normal exponential function, as that is not integer-to-integer. – Lutz Lehmann Dec 01 '16 at 22:21
  • 1
    256 bit, OK. I'm thinking lookup table, as @samgak says, since the function you are actually interested in is `[0..17833] -> UInt256`. – AakashM Dec 01 '16 at 23:09

2 Answers2

1

Use Newton's binomial series

(1+h)^x = 1+x*h + x*(x-1)/2*h^2 + x*(x-1)*(x-2)/6*h^3 + ...
        = 1 + x*h*(1+(x-1)*h/2*(1+(x-2)*h/3*(1+...)))

To get a terminating computation, one would first have to reduce x, I'd think by multiples of log(2)/log(1.01).

Essentially, in the intermediate result you have to use some kind of fixed point arithmetics.

Lutz Lehmann
  • 25,219
  • 2
  • 22
  • 51
1

I would try fixed point. Let assume your Int256 is unsigned 8 bit int then try 8.8 or 8.16 or 8.32 fixed format. Depends on what precision you need.

let rewrite the number to a.b format and assume 8.16 (8.8 ignores too much of the 1.01 binary ones to my taste) so you got:

1.01^x = (1+0.01*65536/65536)^x = (1+655/65536)^x
a=1
b=655

now just compute integer pow for example with power by squaring see:

The result then convert back to integer so either

  • floor (use just a)
  • round (increment a if b>32767 )

To avoid loops just encode the power by squaring into few copy paste lines (one for each bit).

btw this can be done with +,<< if you realize you are multiplying by:

1.01dec = 1.0000001010001111 bin

So you just can do shift and add for each binary 1 instead of mul in case mul is a problem ...

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380