Wednesday, August 12, 2009

FLOOR(x)

Monday, just before I left work, an old problem that had been swirling around in my head decided to surface. Mal and i worked on the RSA challenges (trying to factor really large numbers that are the product of two primes).

So, we found tons of solutions that would get us the answers quickly if we could put our equations into a non-recursive form. Unfortunately, they all used modulo or floor functions, which are conceptual, piecewise functions.

So, back to Monday; As I was packing up to go home, the thought that had occurred to me several times came to the front of my brain again, Integers are periodic. Numbers can be represented in many ways, but fractions make this Integers very clear.

Here is an example:
1.333333333333333(...) is a hard number to write. It could literally take for ever to write it out completely without using fractions. As a fraction though:

1+1/3 is all you need.

so I can talk about parts of it, I will use the following generic format for fractions:

q+(n/d)

where:
q is the "whole" number or the biggest possible number than n/d will allow
n is the numerator and has only the left overs (or remainder)
d is the denominator

What I mean by all of that is, say you had:

0+11/3

Then you are not really in the right form. You would want to simplify the (n/d) or fractional part as much as possible:

3+(2/3)

Is the best answer. But I do digress to my real point, that integers are periodic, or, as the thought actually came to me, cyclical. Integers are special numbers whose fractional part (n/d) is equal to 0.

If integers are cyclical, and the only mathematically cyclical thing I know of is trig functions (specifically sin and cos functions), then maybe I can use them.

I thought, I need to write an equation that is true only when I have hit some point on the unit circle, as i traverse the circumference. So I started looking at the circle and noticed the same thing probably a billion other people have, cos starts at 1 and goes to -1. There had to be something there, so i dropped my victim number into the cos function (with 2pi) and that didn't help me to much.

What did help me was remembering that the cos function always returned a number 1 to -1, no matter how many times you went around the circle. It, in effect, chopped of the whole number (the "q" in my form above) and left a wierd number, that was consistent base on my fractional part, but didn't directly match or seem to directly correlate.

Well, duh! cos is the x axis vector for where you are on the circumference of the unit circle. drop that result back into arccos and it should return how far around the circle my fractional part has taken me.

For instance:

cos(2pi*3.25) = 0
arccos(0) = pi/2

Well, that's not exactly returning just the fractional part of 3.25 (3+1/4) or the 0.25 (0+1.4), but that's because it's scaled by 2pi!

(pi/2)/(2pi) = 0.25

So, now, what if I take my 3.25 - (arccos(cos(2pi*3.25))/(2pi))?

3.25 - (arccos(cos(2pi*3.25))/(2pi)) = 3

Good stuff. I'm well on my way to being able for the equation to tell me if it is an integer or... Wait a second. Didn't that just separate the fractional part from the whole part? Did I just FLOOR that with a real equation? Friggin' wholly grails!

Upon testing there turns out to be a problem though. It works, returning q from q+(0/2) to q+(1/2), but then it sudenly breaks and ramps with a slope of 2 from ther on up to q+(2/2) (or q+1).

Now the problem with this solution emerges. cos is cyclical and get's to -1 half way around the circle, but then starts increasing back towards 1 there after. The arccos function can't tell the difference between the the -0.9 just before we get half way around the circle or just after. The slope of 2 is due to the fact that the rate in change in the number we are testing (3.4, 3.5, 3.6, 3.7, etc) is the same rate of change that is coming out of the arccos function, thusly doubling.

I'm sure I'm rambling and not making a ton of sense, but the important thing that occured to me was that, if I had some sort of indicator that I could use to tell the arccos function to just keep going up, it would work.

Now a few hours after I should have left work, I had developed some imperfect solutions, but the answer was in my grasp.

And with that I leave you with the thrilling cliffhanger of how I developed working equations of the FLOOR(x), CEIL(x), MOD(x,n) functions and much, much more! Untill next time, be sure to drink your Ovaltine!

No comments:

Post a Comment