5
$\begingroup$

In a computer you can't store any real number that you want to because in the $[0.0;1.0]$ interval there are infinite numbers and computer memory is finite. I want to show it in examples, which is why I need some formulas that do some complex calculations and return the initial number. Logically it should be the same but computer will calculate and return a different number. I want to get maximal difference.

Sample expressions can be like $f(x) = x^2/x$ or $(x + x) / 2$

Of course these are too simple ones.

$\endgroup$
  • 1
    $\begingroup$ $x = \ln\ln\ln\ln\ln e^{e^{e^{e^{e^x}}}}$. :-) $\endgroup$ – njguliyev Oct 19 '13 at 18:17
  • $\begingroup$ $(x+1)-1$. On my IEEE 754 double based machine $(2^{53}+1)-1 = 2^{53} - 1$. $\endgroup$ – WimC Oct 19 '13 at 18:37
  • $\begingroup$ Try $\sqrt(9)-3$, I remember seeing a question here where someone asked why this isn't equal to zero on his computer. $\endgroup$ – Spine Feast Oct 19 '13 at 19:02
  • $\begingroup$ @DepeHb That would be a terrible floating-point unit. Normally, when the square root happens to be exactly representable, sqrt() will return the exact result. $\endgroup$ – Daniel Fischer Oct 19 '13 at 19:14
  • $\begingroup$ @njguliyev It returns exactly X after 100000000 iterations. $\endgroup$ – TIKSN Oct 19 '13 at 23:16
3
$\begingroup$

In languages that use IEEE floating point, you can get counterintuitive results with even something as simple as $$1.0-0.3-0.3-0.3-0.1 = -2.77556\times 10^{-17} \neq 0$$

and so for $f(x) = x + 1.0-0.3-0.3-0.3-0.1$, you will have $f(0)\neq 0$.

$\endgroup$
  • $\begingroup$ Thanks @user7530 it works. $\endgroup$ – TIKSN Oct 19 '13 at 23:24
  • $\begingroup$ Note that decimals doesn't suffer from this. This is a direct effect of double/float are binary numbers which in turn means that 0.3 can't be exactly represented creating this effect. Decimal OTOH are what they say they; ie a floating point based around the decimal system and 0.3 can be exactly represented. This is one of many reasons why doubles are a poor choice to represent money. $\endgroup$ – Just another metaprogrammer Oct 21 '13 at 13:10
  • 1
    $\begingroup$ @FuleSnabel Yes exactly. In fact I would argue that money should never be represented using anything but integers (fixed-point decimals). $\endgroup$ – user7530 Oct 21 '13 at 13:34
2
$\begingroup$

I read an interesting sample in Kahan's article: http://www.cs.berkeley.edu/~wkahan/Mindless.pdf

You start from simple definitions:

$x_0 = 4, x_1 = 4.25$

$f y z = 108 - (815 - 1500/z)/y$

And let:

$x_{n+1} = f x_n x_{n-1}$

The resulting series should converge towards 5 but depending on the floating point precision ends up in very different places. For instance of my machine using IEEE 64 doubles with 53 significant bits the computation converges toward 100!

Just to convince myself Kahan is not pulling our legs I redid the computation with bigrationals and then it does converge towards 5.

As you asked for this in the context of computers I hope you don't mind an F# sample program demonstrating the issue

let JMM y z = 108. - (815. - 1500./z)/y

let ApplyJMM n = 
    let mutable a = 4.
    let mutable b = 4.25
    printfn "%f" a
    printfn "%f" b
    for i in 0..n do
        let x = JMM b a 
        a <- b
        b <- x
        printfn "%f" b

ApplyJMM 80

You can try this program without downloading F# by using the interactive compiler: http://www.tryfsharp.org/Create

PS If you are interested in the slightly more complex F# program that uses BigRationals (in order to avoid rounding issues)

// Have to define a bigrational type as F# doesn't have it out of box
type BigRational = bigint*bigint

// The minus operation    
let inline ( --- ) ((lx, ly) : BigRational) ((rx, ry) : BigRational) = 
    let x = lx * ry - rx * ly
    let y = ly * ry
    let gcd = bigint.GreatestCommonDivisor(x,y)
    if gcd.IsOne then x,y
    else (x / gcd),(y / gcd)

// The divide operation    
let inline ( /-/ ) ((lx, ly) : BigRational) ((rx, ry) : BigRational) = 
    let x = lx * ry
    let y = ly * rx
    let gcd = bigint.GreatestCommonDivisor(x,y)
    if gcd.IsOne then x,y
    else (x / gcd),(y / gcd)

// Constructs a BigRational from an integer
let br (i : bigint) : BigRational = i, 1I

let JMM y z = (br 108I) --- ((br 815I) --- (br 1500I)/-/z)/-/y

let ApplyJMM n = 
    let mutable a : BigRational = 4I,1I
    let mutable b : BigRational = 17I,4I
    for i in 0..n do
        let x = JMM b a 
        a <- b
        b <- x

        let t,d = b

        printfn "%s, %s" (t.ToString()) (d.ToString())
ApplyJMM 80
$\endgroup$
  • $\begingroup$ I tried it in Excel and converged to $100$ at $x_{22}$ $\endgroup$ – Ross Millikan Oct 19 '13 at 19:47
  • $\begingroup$ I is not what I need but thank you for your answer. $\endgroup$ – TIKSN Oct 19 '13 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.