2

Let N(x) be the value of the decimal numeral with the fewest significant digits such that x is the double value nearest the value of the numeral.

Given double values a and b, how can we compute the double value nearest N(b)-N(a)?

E.g.:

  • If a and b are the double values nearest .2 and .3,
    • the desired result is the double value nearest .1,
      • 0.1000000000000000055511151231257827021181583404541015625,
    • rather than than the result of directly subtracting a and b,
      • 0.09999999999999997779553950749686919152736663818359375.
Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312
Moritz Roessler
  • 8,542
  • 26
  • 51

3 Answers3

3

As a baseline: In Java, the Double.toString() provides the N(x) function described in the question, returning its value as a numeral. One could take the strings for a and b, subtract them with the elementary-school method, and convert the resulting string to double.

This demonstrates solving the problem is quite feasible using existing library routines. This leaves the task of improving the solution. I suggest exploring:

  • Is there a function D(x) that returns the number of significant digits after the decimal place for the numeral described in N(x)? If so, can we multiply a and b by a power of ten determined by D(a) and D(b), round as necessary to produce the correct integer results (for situations where they are representable as double values), subtract them, and divide by the power of ten?
  • Can we establish criteria for which b-a or some simple expression can be quickly rounded to something near a decimal numeral, bypassing the code that would be necessary for harder cases? E.g., could we prove that for numbers within a certain range, (round(10000*b)-round(10000*a))/10000 always produces the desired result?
Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312
0

You can convert to 'integers' by multiplying then dividing by a power of ten:

(10*.3 - 10*.2)/10 == 0.1000000000000000055511151231257827021181583404541015625

It may be possible to work out the appropriate power of ten from the string representation of the number. @PatriciaShanahan suggests looking for repeated 0's or 9's.

Consider using a BigDecimal library such as javascript-bignum instead.

tom
  • 21,844
  • 6
  • 43
  • 36
  • 1
    Most `double` values near numerals such as 3.14 have bits set in or near the low bit of the significand, so they cannot be multiplied by more than a small power of 10 before encountering rounding errors. E.g., `10*3.14` is not ten times the value of `3.14`. – Eric Postpischil May 24 '13 at 00:48
  • You could use `Math.pow(10,Math.max ("".split.call(a,".")[1].length,"".split.call(b,".")[1].length))` to get the desired power of 10. The point is, is there a prove that this yields **always** the desired result or is there **any** 2 values, where this does not apply? – Moritz Roessler May 24 '13 at 09:44
0

You could also inquire in Smalltalk Pharo 2.0 where your request translates:

^(b asMinimalDecimalFraction - a asMinimalDecimalFraction) asFloat

Code could be found as attachment to issue 4957 at code.google.com/p/pharo/issues - alas, dead link, and the new bugtracker requires a login...

https://pharo.fogbugz.com/f/cases/5000/Let-asScaledDecimal-use-the-right-number-of-decimals

source code is also on github, currently:

https://github.com/pharo-project/pharo-core/blob/6.0/Kernel.package/Float.class/instance/printing/asMinimalDecimalFraction.st

The algorithm is based on:

Robert G. Burger and R. Kent Dybvig
Printing Floating Point Numbers Quickly and Accurately
ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation
June 1996.
http://www.cs.indiana.edu/~dyb/pubs/FP-Printing-PLDI96.pdf

aka.nice
  • 9,100
  • 1
  • 28
  • 40