Thread Subject:

How to avoid wrong answers in simple arithmetic expressions.

I tried the following cody problem for fun:
[quot]
Given an amount of currency, return a vector of this form:

 [100 50 20 10 5 2 1 0.5 0.25 0.1 0.05 0.01]

Example:

 Input a = 257.68
 Output b is [2 1 0 0 1 1 0 1 0 1 1 3]

Always use bigger bills/coins if possible.
[/quot]

My solution:
function b = makingChange(a)
   v = [100 50 20 10 5 2 1 0.5 0.25 0.1 0.05 0.01];
   for i = 1 : length(v)
      b(i) = floor(a/v(i));
      a = a - b(i)*v(i);
   end
end

But, due to rounding error, this gives a wrong answer for example for a = 135.01.
The problem does not go away even if I replace the last line by a = rem(a, v(i)).
How does one avoid such issues in general?

On 1/19/2013 1:04 AM, SK wrote:
...

> But, due to rounding error, this gives a wrong answer for example for a
> = 135.01.
> The problem does not go away even if I replace the last line by a =
> rem(a, v(i)).
> How does one avoid such issues in general?

Scaling and/or fixed point are common techniques...

--

On 1/19/2013 7:53 AM, dpb wrote:
...

>
> Scaling...[and other stuff elided for time being]
>

What happens if you were to multiply v by 100 and do the same w/ the
input variable internal to the function before you start your loop?

--

dpb <none@non.net> wrote in message <kdeaav$3e3$1@speranza.aioe.org>...
> On 1/19/2013 7:53 AM, dpb wrote:
> ...
>
> >
> > Scaling...[and other stuff elided for time being]
> >
>
> What happens if you were to multiply v by 100 and do the same w/ the
> input variable internal to the function before you start your loop?
>
> --

Thanks for the suggestion.

Yes, I did try this, and it gives the correct result although I'm not sure I understand why. My first thought was that operations on numbers which differed only in the base 10 exponent should give results of equal accuracy.

However, looking up the IEEE 754 floating point floating point representation. I see that the exponent is a power-of-2 exponent rather than a power-of-10. So, for example, 0.09 and 9 have very different mantissa's. Nevertheless both 0.09 and 9 do not have exact IEEE 754 representations. More generally, most integers do not have an exact representation in this format.

So, does Matlab treat small integers in a special way?
Otherwise why would multiplying the numbers by 100 in the original problem guarantee a correct solution?

Best Regards.

"SK " <modysk@hotmail.com> wrote in message <kdf25b$sqv$1@newscl01ah.mathworks.com>...
> dpb <none@non.net> wrote in message <kdeaav$3e3$1@speranza.aioe.org>...
> > On 1/19/2013 7:53 AM, dpb wrote:
> > ...
> >
> > >
> > > Scaling...[and other stuff elided for time being]
> > >
> >
> > What happens if you were to multiply v by 100 and do the same w/ the
> > input variable internal to the function before you start your loop?
> >
> > --
>
> Thanks for the suggestion.
>
> Yes, I did try this, and it gives the correct result although I'm not sure I understand why. My first thought was that operations on numbers which differed only in the base 10 exponent should give results of equal accuracy.
>
> However, looking up the IEEE 754 floating point floating point representation. I see that the exponent is a power-of-2 exponent rather than a power-of-10. So, for example, 0.09 and 9 have very different mantissa's. Nevertheless both 0.09 and 9 do not have exact IEEE 754 representations.

False. 9 has an exact IEEE double representation. 0.09 does not ... the closest is:

0.0899999999999999966693309261245303787291049957275390625

> More generally, most integers do not have an exact representation in this format.

False. All of the integers in the range of your particular problem can be represented exactly in IEEE double. All integers from 0 up to 2^53 have exact IEEE double representations.

> So, does Matlab treat small integers in a special way?

No. They are treated just like all other IEEE double numbers.

> Otherwise why would multiplying the numbers by 100 in the original problem guarantee a correct solution?

Multiplying by 100 (and rounding the results) puts everything into integers that can be represented exactly by IEEE double.

To get some help visualizing all of this, I suggest you download the following utility from the FEX:

http://www.mathworks.com/matlabcentral/fileexchange/22239-num2strexact-exact-version-of-num2str

James Tursa

"James Tursa" wrote in message <kdfc0c$v7$1@newscl01ah.mathworks.com>...

> False. 9 has an exact IEEE double representation. 0.09 does not ... the closest is:
>
> 0.0899999999999999966693309261245303787291049957275390625
>
> > More generally, most integers do not have an exact representation in this format.
>
> False. All of the integers in the range of your particular problem can be represented exactly in IEEE double. All integers from 0 up to 2^53 have exact IEEE double representations.

OK. I got it (after some embarrassment). The IEEE 754 format description on Wikipedia was a bit confusing - all those negative powers of 2! It really boils down to - if a number can be represented as a sum of powers of 2, then it has an exact representation - so all integers (within some range) will have an exact representation.

Nevertheless, it does appear that exact calculations even with integers has to be thought through on a case by case basis.

Best Regards.

> > So, does Matlab treat small integers in a special way?
>
> No. They are treated just like all other IEEE double numbers.
>
>
> James Tursa

"SK " <modysk@hotmail.com> wrote in message <kdgb24$a74$1@newscl01ah.mathworks.com>...

>
> OK. I got it (after some embarrassment). The IEEE 754 format description on Wikipedia was a bit confusing - all those negative powers of 2! It really boils down to - if a number can be represented as a sum of powers of 2, then it has an exact representation - so all integers (within some range) will have an exact representation.

Not exactly. 1 + 2^(-100) cannot be represented by IEEE 754.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kdgfie$of7$1@newscl01ah.mathworks.com>...
> "SK " <modysk@hotmail.com> wrote in message <kdgb24$a74$1@newscl01ah.mathworks.com>...
>
> >
> > OK. I got it (after some embarrassment). The IEEE 754 format description on Wikipedia was a bit confusing - all those negative powers of 2! It really boils down to - if a number can be represented as a sum of powers of 2, then it has an exact representation - so all integers (within some range) will have an exact representation.
>
> Not exactly. 1 + 2^(-100) cannot be represented by IEEE 754.
>
> Bruno

Note that I said _integers_ within some range.

Best Regards.

"SK " <modysk@hotmail.com> wrote in message <kdggro$sbt$1@newscl01ah.mathworks.com>...

>
> Note that I said _integers_ within some range.
>

It's not a question of range either: 2^-100 can be represented by IEEE.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kdgh70$55$1@newscl01ah.mathworks.com>...
> "SK " <modysk@hotmail.com> wrote in message <kdggro$sbt$1@newscl01ah.mathworks.com>...
>
> >
> > Note that I said _integers_ within some range.
> >
>
> It's not a question of range either: 2^-100 can be represented by IEEE.
>
> Bruno

I didn't say anything about 2^-100 or any such fractional number, so I'm not sure what your point is.

OK if you don't like negative power I give you an example of positive power that contradict what you said:
[The IEEE 754 format description on Wikipedia was a bit confusing - all those negative powers of 2! It really boils down to - if a number can be represented as a sum of powers of 2]

Which is wrong statement. Why, because:

2^100 can be represents by IEEE
(2^100 + 1) cannot.

Both are sum of power of 2.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kdghtg$2gl$1@newscl01ah.mathworks.com>...
> OK if you don't like negative power I give you an example of positive power that contradict what you said:
> [The IEEE 754 format description on Wikipedia was a bit confusing - all those negative powers of 2! It really boils down to - if a number can be represented as a sum of powers of 2]
>
> Which is wrong statement. Why, because:
>
> 2^100 can be represents by IEEE
> (2^100 + 1) cannot.
>
> Both are sum of power of 2.
>
> Bruno

All right, suppose I say all integers between -2^52 and 2^52 can be represented exactly - I did say "within some range" without specifying what that range was. But I get your point, which I presume is that - not all integers from realmin to realmax can be exactly represented - a fact that can easily be forgotten in haste.

Best Regards.

"SK " <modysk@hotmail.com> wrote in message <kdgkg1$a14$1@newscl01ah.mathworks.com>...
>
> All right, suppose I say all integers between -2^52 and 2^52 can be represented exactly - I did say "within some range" without specifying what that range was.

That's better.

All integers are sum of powers of 2 (or powers of x, x is whatever you like), so there is no point in involving the basis when discussing integer in floating-poimt coding. The range 2^52 come from the fact that 52 bit is used by the mantissa of double precision IEEE.

Very often miss-believing occur when user manipulate fractional number such as 0.1. The number 0.1 = 1/10 = 1/(2*5) cannot be represented exactly in binary basis, and human notation for 0.1 happens to be finite because we count in 10 basis. On the other hand 0.1 cannot be codded finitely in binary basis (computer), just like 1/3 cannot be written with finite decimal digit numbers. Therefore non-accuracy occurs in arithmetic operations for decimal fractional numbers.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kdgm4e$f19$1@newscl01ah.mathworks.com>...
> "SK " <modysk@hotmail.com> wrote in message <kdgkg1$a14$1@newscl01ah.mathworks.com>...
> >
> > All right, suppose I say all integers between -2^52 and 2^52 can be represented exactly - I did say "within some range" without specifying what that range was.
>
> That's better.
>
> All integers are sum of powers of 2 (or powers of x, x is whatever you like), so there is no point in involving the basis when discussing integer in floating-poimt coding. The range 2^52 come from the fact that 52 bit is used by the mantissa of double precision IEEE.
>
> Very often miss-believing occur when user manipulate fractional number such as 0.1. The number 0.1 = 1/10 = 1/(2*5) cannot be represented exactly in binary basis, and human notation for 0.1 happens to be finite because we count in 10 basis. On the other hand 0.1 cannot be codded finitely in binary basis (computer), just like 1/3 cannot be written with finite decimal digit numbers. Therefore non-accuracy occurs in arithmetic operations for decimal fractional numbers.
>
> Bruno

Thank you for your help.

By the way the following is from the Wikipedia article on IEEE 754 - 1985
(http://en.wikipedia.org/wiki/IEEE_754-1985)
"In 1976 Intel began planning to produce a floating point coprocessor. Dr John Palmer, the manager of the effort, persuaded them that they should try to develop a standard for all their floating point operations. William Kahan was hired as a consultant; he had helped improve the accuracy of Hewlett Packard's calculators. Kahan initially recommended that the floating point base be decimal[8] but the hardware design of the coprocessor was too far advanced to make that change."

Perhaps it would have been more "human" for the floating point base to be in decimal. Not sure of any other consequences though.

Best Regards.