implement log2, log10, log256 (and possibly ln)

[diwu1989]

Can there be a natural log or base 2 log implemented?
Thanks

[A-ndy-git]

+1. Also been looking for this functionality for some time.

I'm unsure of the best method to implement this?

[elee1766]

there are a few different solidity libraries that implement logarithm. off the top of my head, the big name i know is oz, they have log2,log10,log256 in their math libraries: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/math/Math.sol
log10 i think is used in their word -> ascii string function.

it may be desirable to replicate the results (not method, we can probably do better) of one such library (not neccesarily oz's), since I think mirroring or performing on-chain operations is a common use case for this package.

[diwu1989]

+1 yes, that was my reasoning for requesting this, because I wanted to match some of the LOG math used in smart contracts

[elee1766]

+1 yes, that was my reasoning for requesting this, because I wanted to match some of the LOG math used in smart contracts

happy to do some work on this. personally we use log2

which LOG math functions do you have immediate needs for? i can start with those and add more down the line

log2? log10? log256?

[diwu1989]

Log2 is enough for UniswapV3 tickmath:
https://github.com/Uniswap/v3-core/blob/main/contracts/libraries/TickMath.sol

[holiman]

Is there any difference between Log2() and BitLen()? Because the latter exists already...

[karalabe]

Is there any difference between Log2() and BitLen()? Because the latter exists already...

Yes, BitLen is int(log2). But if you want to calculate logB(N), you need log2(N)/log2(B) with full float representation, not truncated to int.

[karalabe]

FWIW, here's a set of log implementation for big.Int https://github.com/robpike/ivy/blob/master/value/log.go

[holiman]

Possible api-methods could be

(z *Int) IntLog2( ... ) *Int
(z *Int) IntLog10( ... ) *Int

(z *Int) Log2( ... ) float64
(z *Int) Log10( ... ) float64

However, it would be simpler to just do

(z *Int) IntLog2( ... ) *Int
(z *Int) IntLog10( ... ) *Int

(z *Int) Float64() float64

Then the caller can just do math.Log2(myint.ToFloat64()) to deal in floats. The math package already has it all.

Also, in fact, the IntLog methods could return a smaller uint type, e.g. uint64, because even a log2 of a uint256 will never exceed 256 in size. So no need to return *Int.

[elee1766]

@diwu1989 @holiman

https://gfx.cafe/-/snippets/10#LC16

the log2 required in uniswap is just msb, so bitlen - 1

at the very least it's correct when going from tick -> sqrt price -> tick

iirc msb is always bitlen - 1. if thats the case i dont see a use in adding a dedicated msb function

[holiman]

Yeah implementing Log2 and Log256 is pretty trivial, but implementing Log10 is a bit more fun.

[elee1766]

uniswap does log1.0001 through using uint256 as a fixed point number. perhaps that is something to consider? although computers are not evm so maybe its not as great.

[holiman]

Log10 implemented by #136
Float64 implemented by #132

If anyone wants to add Log2 and Log256, it's welcome. Otherwise, I think most users can just use the existing BitLen. I'll close this as 'done'.