Can't solve function to variable fast

I have the function 254/319 = (y^3/319)-floor(y^3/319).I want to check if the decimal behind Y^3/319 (y = 100 > 3134,796...) is the same as 254/319 (0,796...). (true in this case) I want to find y = 100 faster than a while loop with y = y+1, is there an alternative method to this? Thanks in advance

Answer 1

[John D'Errico]

Huh? You should NEVER use floating point computations here.

You want to find y (the smallest y, if more than one exists) such that this

254/319 = (y^3/319)-floor(y^3/319)

is true?

Multiply by 319. This reduces to finding y such that

mod(y^3,319) == 254

where we are looking for the smallest positive integer y that satisfies the requirement.

So you are looking for an integer cube root of 254, modulo 319. I think I recall that a variation of the Shanks-Tonelli algorithm can be used here.

https://en.wikipedia.org/wiki/Cubic_reciprocity

https://en.wikipedia.org/wiki/Tonelli–Shanks_algorithm

For small moduli, of course it will be simplest to just use brute force.

find(mod((1:318).^3,319) == 254)
ans =
   100

Note that here I never had to work with fractional values. All values were purely flints, thus floating point integers.

But if we ask for an integer solution to the congruential equation:

mod(y^3,4514534542343) == 3341524088176

this may take some effort. So do some reading about Shanks-Tonelli, and how to modify it to handle cube roots. That is off-topic for Answers of course. Note that for large moduli, you might need to work with a large integer tool, so either syms or my own vpi tools might be appropriate. Even uint64 will be severely limited, once you start cubing large integers. (Yes, I suppose I could have written a modular cube root code in my toolbox.)

Answer 2

[Rik]

y=1:1000;
valid_y=find(rem(y.^3,319)==254);

Like this?

[Rik]

Btw, you should be really careful with comparing decimal values. Computers can have difficulty with them, because of how a float is stored in memory. If two operations have a slightly different method of rounding you can get into trouble. Some times the only way is not to check a==b but abs(a-b)<eps (eps is the function that tells you the precision of a value)