How to calculate log16 of a 256 bit Integer in Golang

Question

how to get the log with base 16 for a math/big Int variable.

Any help would be great since I am new to Go and came from Python and C environment

s := "c6d86e5a2cb4bc532361c2d4940f0b1a0138066e25d65c1c530d080b11f8ca24" // Hex value
i := new(big.Int)
i.SetString(s, 16) // hex value to Big Int
// how to get the log with base 16 for a math/big Int variable.

How it works in python

import math 
a = 0xc6d86e5a2cb4bc532361c2d4940f0b1a0138066e25d65c1c530d080b11f8ca24
a>> 89940344608680314083397671686667731393131665861770496634981932531495305005604L
math.log(a)/math.log(16.0)

answer turns out to be 63.908875905794794

score 4 · Answer 1 · answered Oct 22 '18 at 02:35

There is specific approach for log16 and hex input without long arithmetics.

To get integer (floored) result, just count hex digits. In this case there are 63 digits, so you have

  FloorLog16 = 63

Now get 8 first digits (more to enhance precision)

  b = 0xc6d86e5a

and get log16

 p = log(b) / log(16) = 7.908875905775919

Use fractional part of this result to make logarithm more exact

fp = p - Floor(p) = 0.908875905775919
log16(0xc6d86e5a2cb4bc532361c2d4940f0b1a0138066e25d65c1c530d080b11f8ca24) = 
      63 + 0.908875905775919 = 63.908875905775919

Note 12 exact digits

Max von Hippel · Answer 2 · 2018-10-21T21:30:41.227

An interesting property of logarithms is that change-of-base is actually pretty easy.

log_b (x) = log_a (x) / log_a (b)

So if you want to get log_16 (x), you could use the Log function and do change of base:

log_e (x) = log_16 (x) / log_16 (e)
log_16 (e) = approximately 0.36067 
=> log_16 (x) = 0.36067 * log_e (x)

So in Go, I think this would be:

li := Log(i) * 0.36067

Edit: When I wrote the answer above I did not realize that Log wouldn't work on a Big Int. Reading the Go Github, it looks like this is a requested feature in the language which has not yet been implemented due to lack of a satisfactorily quick solution. From what I read it looks like the best solution for the moment, if you must use a Big Int, is probably a Taylor Series implementation, which in my opinion would be non-trivial to write. The thread I linked to indicates that one or more such implementations may exist but are not necessarily computationally correct.

log function accepts float64 type parameters but I have a big Int — Mohit Gupta, Oct 21 '18 at 16:48
@MohitGupta gotcha! Then my answer is insufficient. I'll take a look this afternoon; hopefully someone else will figure it out before then. — Max von Hippel, Oct 21 '18 at 16:50

chriopp · Answer 3 · 2018-10-21T18:10:27.537

1

First you need to convert the hex string to the correct hex notation by adding "0x" at the beginning. Next write a log16 method, use strconv to get the integer, than float64 for the input of the log method. Caution: this solution does not deal with integer overflow.

package main

import (
    "fmt"
    "math"
    "strconv"
)

func log16(x float64) float64 {
    return math.Log(x)/math.Log(16.0)   
}

func main() {
    s := "c6d86e5a2cb4bc532361c2d4940f0b1a0138066e25d65c1c530d080b11f8ca24"
    s1 := "0x" + s
    h, _ := strconv.ParseInt(s1,0,64)
    fmt.Println(log16(float64(h)))

}

edited Oct 21 '18 at 18:10

answered Oct 21 '18 at 17:18

chriopp

947
7
12

The bits overflow float64, the number is really big for it. Check my edit for the question. – Mohit Gupta Oct 21 '18 at 17:34
answer turns out to be 15.75 but should be 63.908875905794794 – Mohit Gupta Oct 21 '18 at 17:52
Sorry, did not think about that. I'm not aware of any existing implementation. There is the package`math/big/decimal` and an implementation to solve the natural logarithm in java in https://stackoverflow.com/questions/739532/logarithm-of-a-bigdecimal, maybe you can go from there. – chriopp Oct 21 '18 at 18:08

How to calculate log16 of a 256 bit Integer in Golang

3 Answers3