Evaluating +-*/, pow, root, log, exp tree of big-fixed?


#1
  1. I know about https://github.com/rust-num/num-bigint and https://github.com/rust-num/num . The correct answer I am looking for is more likely to be an algorithm than a crate

  2. Using bigint, we can defined bigfloat (which is (bignum, n) representing bignum * 10^n)

  3. Now, suppose we ahve an expression tree consisting of bigfloat, ±*/, pow, root, log, exp … and I want to say:

evaluate this tree to K significant digits, i.e. get an output of the form:

a_0 . a_1 a_2 … a_k * 10^M for some M and a_0, a_1, …, a_k

  1. Question: what algorithm do we use for this? I don’t think converting each bigfloat to an f64 provides the type of precision guarantee we want.

Thanks!


#2

Whatever you do, it will have to be iterative/adaptive with feedback because subtraction, root, etc. convert numbers with N digits of significance to results with fewer significant digits. Thus to get K significant digits in the final result you need to be prepared to repeat the computation with increasing significance of the intermediary results.


#3

@TomP That’s a really useful "negative "insight. You’re basically saying

a - b == (10^N + a) - (10^N + b)

So as a result, I can’t just “make one pass through the tree bottom up”, because it’s not clear how many digits we need to keep. It’s only when we hit the “`” that we get the “oh $&#(” moment and realize the two numbers are really realy close and thus we need more digits on both #'s.

I feel like this has to be a well studied problem in CS. Any idea on what terms to google for?


#4

Perhaps google “loss of significance error” and use the search results as a basis for further search.