Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
How to avoid wrong answers in simple arithmetic expressions.

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: SK

Date: 19 Jan, 2013 07:04:08

Message: 1 of 14

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?

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: dpb

Date: 19 Jan, 2013 13:53:48

Message: 2 of 14

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...

--

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: dpb

Date: 19 Jan, 2013 14:24:43

Message: 3 of 14

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?

--

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: SK

Date: 19 Jan, 2013 21:11:07

Message: 4 of 14

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.

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: James Tursa

Date: 19 Jan, 2013 23:59:08

Message: 5 of 14

"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

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: SK

Date: 20 Jan, 2013 08:49:08

Message: 6 of 14

"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

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: Bruno Luong

Date: 20 Jan, 2013 10:06:06

Message: 7 of 14

"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

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: SK

Date: 20 Jan, 2013 10:28:08

Message: 8 of 14

"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.

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: Bruno Luong

Date: 20 Jan, 2013 10:34:08

Message: 9 of 14

"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

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: SK

Date: 20 Jan, 2013 10:36:08

Message: 10 of 14

"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.

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: Bruno Luong

Date: 20 Jan, 2013 10:46:08

Message: 11 of 14

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

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: SK

Date: 20 Jan, 2013 11:30:09

Message: 12 of 14

"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.

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: Bruno Luong

Date: 20 Jan, 2013 11:58:06

Message: 13 of 14

"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

Subject: How to avoid wrong answers in simple arithmetic expressions.

From: SK

Date: 20 Jan, 2013 12:18:08

Message: 14 of 14

"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.

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us