Turing "mod" fail

[Dreadnought]

So you want to test for perfect cubes. You can take the cube root of a number and get a real number.

You are trying to check if the real value is an integer, however, real numbers are, at times, imperfect so this only works with a few cubes (1, 27 and 216 for numbers between 1 and 1000 it seems).

The mod operator can't really do much better. You know how to round that real number to an integer. Try to think of some way to use the rounded cube root to check if the original number was indeed a perfect cube.

[Aange10]

Do mods in all languages do that?

[mirhagk]

depends on the langauge. In some cases mod only works on integers, in other cases it just does weird things with real numbers.

[Aange10]

That's actually very interesting. I wonder why that is... could you elaborate?

[Dreadnought]

Well, modular arithmetic is only defined for integers so how you extend the concepts into real numbers is not clear. For example, say you had a theorem in modular arithmetic that requires a number to be prime. How do you extend this to real numbers?

[mirhagk]

the way the computer handles mod for integers is actually the exact same way they handle division (it's actually calculated at the same time). Floating point numbers are handled completely different, and are not precise.

Basically if your program relies on modular arithmetic for real numbers, change your program.

[Aange10]

Interesting, thank you both. What about 125 ** 1/3 not= 5?

[evildaddy911]

because 5 is an integer, whereas 125 ** 1/3 is a real number, 125 ** 1/3 will never equal "5"

[Dreadnought]

evildaddy911 wrote:

because 5 is an integer, whereas 125 ** 1/3 is a real number, 125 ** 1/3 will never equal "5"

Although that does seem to be a valid explanation, I'm afraid it is not.

Notice this

Turing:

for i: 1..10     put i, "  ", (i ** 3) ** (1/3) = i end for % The result is 1  true 2  false 3  true 4  false 5  false 6  true 7  false 8  false 9  false 10  false

Notice that the cube roots of 1, 27and 216 are actually equal to 1, 3 and 6 even though the roots are real and 1, 3 and 6 are not.

The true reason is that real numbers are not perfectly accurate (they only store so many digits). The Wikipedia page has a nice example for 1/3.

Try this

Turing:

var num : real := 125 ** (1 / 3) put frealstr(num, 16,15) var num2 : real :=216 ** (1 / 3) put frealstr(num2, 16,15) % Result 5.00000000000000088817841970012523233890533447265625 6.00000000000000000000000000000000000000000000000000

Basically, 216 ** (1/3) (don't forget that 1/3 is a real too) happens to come out as 6 exactly once it is rounded (usually real numbers have 16 digits of accuracy). But this is not so for 125.

Hope this clear thing up.

[Aange10]

I knew that evildaddy, i didn't mean the typespecs to be equal, i meant the value.

@Dread, so the value of 125 ** 1/3 is 5.00000000000000088817841970012523233890533447265625, not because of exponential function, but because of the inaccuracy of 1/3 (.3repeating)?

[Tony]

Aange10 @ Sun May 06, 2012 5:00 pm wrote:

@Dread, so the value of 125 ** 1/3 is 5.00000000000000088817841970012523233890533447265625, not because of exponential function, but because of the inaccuracy of 1/3 (.3repeating)?

Kind of, but probably not for the reasons that you are thinking of. See http://en.wikipedia.org/wiki/IEEE_754 for the standard in how floating-point numbers are actually represented:

Quote:

(-1)^s * c * b^q

Where the base b is typically 2 (binary representation of the number). As such, there is simply no exact mapping between some decimal fractions and binary encodings. For what integer values of c and q would

code:

0.1 = c * 2^q

be true?

So something like 1/10 is just as problematic as 1/3.

A way to deal with this is to never compare numbers directly, but only with less-than and greater-than checks, within deltas. In the quoted example, 125 ** 1/3 is less than 0.000000000000001 away from 5.0. If that is acceptable for your calculations, you can just call it 5.0. Some languages have that build in.

[Amarylis]

So, would doing something like...

[syntax="turing]if num > 5 and num < 5.000001 then
num := 5
end if[/syntax]


Solve the problem for 125 ** (1/3)? (What would be a better solution for this though?)

[Dreadnought]

Dreadnought wrote:

You know how to round that real number to an integer. Try to think of some way to use the rounded cube root to check if the original number was indeed a perfect cube.

Here I was hinting at a simple way of doing things. Say I give you 28, you compute 28 ** (1/3) and round it to an integer, this gives you 3. How can you easily figure out if 3 is the cube root of 28? (which will tell you if 28 is a perfect cube)

[evildaddy911]

if a ** b = c then
c ** (1 / b) = a
end if

[Dreadnought]

evildaddy911 wrote:

if a ** b = c then
c ** (1 / b) = a
end if

Except when b = 0.
But that's the idea.

This gives an easy check for a perfect cube

Turing:

if (round (a ** (1/3)) ** 3) = a then    put "a is a perfect cube" end if