# Thread: Least amount of operations to convert an 18th of a second into a 30th.

1. ## Least amount of operations to convert an 18th of a second into a 30th.

Okay, so i'm writing a program in assembly language to calculate a simple frame delay.
It uses the real time clock which ticks at a resolution of 18.2 times a second. (1/18 of a second)
The code simply counts the number of times the cpu can execute a loop before the RTC ticks again. (the loop begins immediately after a tick)

The cpu architecture is 16 bit, so let's just say variable X takes the single units place value, and variable Y takes the 64K (65,536) place value.
Every time X reaches 65,535, it is reinitialized to 0, and Y (which begins at 0) is incremented.

The max count (64K^2)-1 is a 32 bit number, this particular CPU architecture provides easy instructions to multiply and divide 32 bit numbers.
However, adding, and subtracting 32 bit numbers is a little convuluted, so i'm trying to avoid doing that.

A delay of 1/18th of a second obviously results in a framerate locked at 18 fps, not very useful.
So, as input the code takes a constant number. It's a simple frame rate multiplier.
If passed 2, the code will divide 1/18 into 2 resulting in a delay that lasts 1/36th of a second. (36 fps)
This is all well and good, but the problem is that frame rates of both 36, and 54 (1/(18*3)) don't look very good at standard monitor refresh rates. (screen tearing)

So, what I need to do is extract from 1/18th of a second, using only division and multiplication operations (factors and multiples), 1/30th of a second. In the shortest amount of operations.
The division instruction returns only a whole number and a remainder. I can't use floating point numbers.

2. Originally Posted by codyw1996
Okay, so i'm writing a program in assembly language to calculate a simple frame delay.
It uses the real time clock which ticks at a resolution of 18.2 times a second. (1/18 of a second)
The code simply counts the number of times the cpu can execute a loop before the RTC ticks again. (the loop begins immediately after a tick)

The cpu architecture is 16 bit, so let's just say variable X takes the single units place value, and variable Y takes the 64K (65,536) place value.
Every time X reaches 65,535, it is reinitialized to 0, and Y (which begins at 0) is incremented.

The max count (64K^2)-1 is a 32 bit number, this particular CPU architecture provides easy instructions to multiply and divide 32 bit numbers.
However, adding, and subtracting 32 bit numbers is a little convuluted, so i'm trying to avoid doing that.

A delay of 1/18th of a second obviously results in a framerate locked at 18 fps, not very useful.
So, as input the code takes a constant number. It's a simple frame rate multiplier.
If passed 2, the code will divide 1/18 into 2 resulting in a delay that lasts 1/36th of a second. (36 fps)
This is all well and good, but the problem is that frame rates of both 36, and 54 (1/(18*3)) don't look very good at standard monitor refresh rates. (screen tearing)

So, what I need to do is extract from 1/18th of a second, using only division and multiplication operations (factors and multiples), 1/30th of a second. In the shortest amount of operations.
The division instruction returns only a whole number and a remainder. I can't use floating point numbers.
1/18 = 5/3 * 1/30

3. I have no clue what this question is asking mathematically.

The OP seems to want to evaluate the function

$y = f(x) = \left \lfloor \dfrac{30x}{18} \right \rfloor + \left \lfloor 2 * \left ( \dfrac{30x}{18} - \left \lfloor \dfrac{30x}{18} \right \rfloor \right ) \right \rfloor,$

where x is a non-negative integer, without using addition or subtraction. I doubt it is possible. Of course, I may not understand the question.

4. Originally Posted by JeffM
I have no clue what this question is asking mathematically.

The OP seems to want to evaluate the function

$y = f(x) = \left \lfloor \dfrac{30x}{18} \right \rfloor + \left \lfloor 2 * \left ( \dfrac{30x}{18} - \left \lfloor \dfrac{30x}{18} \right \rfloor \right ) \right \rfloor,$

where x is a non-negative integer, without using addition or subtraction. I doubt it is possible. Of course, I may not understand the question.

Sorry, i'm not great at explaining things.

Ok, let's say that after 1/18th of a second has passed, I have counted the following number of loops.
(I'll use the X & Y variables mentioned in my question. But i'll rename them to num64K & numOnes):

num64K = 27 (in other words 65,536*27)
numOnes = 42,875
(I have to split any number larger than 65,536 up into place values like this, since the 16 bit CPU cannot hold a singular larger number.)

This means that in 1/18th of a second, I have looped a total of num64K+numOnes times. (65,536*27+42,875=1,812,347)
So, if I invert the loop and execute it in reverse, (decrementing is the same speed as incrementing) it will always take 1/18th of a second to count back down from 1,812,347 to 0.

Okay, so if I divide the total loop count into 2, i'll end up with:

num64K = 13
numOnes = 54,205

So, this means that my total loop count when given 1/18*2 (1/36th) of a second is 65,536*13+54,205 = 906,173
(1,812,347/2 is actually 906,173.5, but I'm working with whole numbers on a computer, everything after the decimal point is thrown away)

So, by multiplying and dividing this number of loops I can infer the number of times I can loop if given some other amount of time.

Do you see what i'm saying now?
If the only information I have is the number of times I can loop in a given 18th of a second. (65,536*27+42,875 times)
How do I use that information to figure out the number of times I can loop if given only a 30th of a second
without using addition, subtraction, or floating point division. (only multiplication and remainder division)
In the shortest number of operations.

One solution i've thought about is:
1/18*6 = 6/18 = 1/3 ÷ 10 = 1/30 This accomplishes it in one multiplication, and one division. (I literally just thought about this at the time of posting this reply. It's probably the best solution.)

So, now you see what i'm saying, I have to use factors and multiples of the denominator to get there.

I'm also interested in some more exotic frame rates, like frames that last 1/75th of a second (roughly the refresh rate of many MS-DOS games on old CRT's) and 1/24th (the slowest acceptable frame rate, for older machines.

5. Originally Posted by Denis
n = 65,536*27+42,875 = 1,812,347
1/18 : n
1/30 : n / (1/18) * (1/30) = 1,087,408

Too simple...so I'm missing something...

I'm confused. What are you trying to say exactly?
What's the colon supposed to represent in "1/18:n"? A ratio?
I dropped out of school, I really missed a lot of formal math. I don't understand.

I think I kinda see what you're saying, but there's no easy way of just doing this " n / (1/18) * (1/30) = 1,087,408"
It's assembly language programming, so you can't just work with fractions directly.

For instance 1/18 as a fraction is just 0 remainder 1, and 1/30 is 0r1.

You can only multiply and divide the whole number "n" by other whole numbers.

As I mentioned above n*6/10=1,087,408 is one solution, but I just happened to think of it. I didn't do any math other than looking up a list of factors of 18.
I'm looking for a way to do this to arive at 1/75th & 1/24th of a second.

Obviously there is an easy solution multiply 1/18th by 18 to get the number of loops I can execute in a full second.
From there all you have to is divide the loop count by any number to derive the frame delay. If w is any 16 bit whole number, then 18/18/w = 1/w (w fps)

The problem with that is some CPUs are so fast that a second is enough time to loop more than the max value that can be held in 32 bits.
If it worked, this method would always guarantee the calculation of any frame delay in 2 operations. 1/18 * 18 = 1 ÷ n = 1/n, but unfortunately it's buggy.

6. Look. We really want to help you. And some of us at various times in our career have done things with computers. But to answer a math question, we need to translate the practical problem into mathematical terms. You are probably giving us much more detail about the technical problem than we need, but not enough about the mathematical aspects of that problem

Let's talk first about function notation. It looks something like this

$w = f(x,\ y,\ z)$

That just means that there is a mathematical procedure, a formula or algorithm, called f, where x, y, and z are input numbers and w is the output number. It looks to me as though you want to find what that formula or algorithm is without using addition or subtraction. I can't promise that there is such a thing because you are requesting that we abandon half of arithmetic.

In any case, we don't know what you want the function to do. I am not even sure how many inputs there are. You spend a lot of time telling us why you want to do something, but not what you want to do. Probably the best way to proceed is for you to give us a few numeric examples: what are the input values for each example and what you want to see as an output for each example. And in the examples don't worry about what the computer can do; show us the arithmetic that you want to go from input to output. We get that at the end of the day whatever we come up with has to fit within the constraints of what the computer can do, but we first have to know what needs to done by the arithmetic.

Programmers like to assign names to variables for purposes of documentation. Mathematicians like to assign letters to variables. Help us out by using letters, not names.

Finally, we understand about truncation. We even have a way to write it.

$\left \lfloor \dfrac{100}{18} \right \rfloor = 5.$

Notice in that example that the result of the division is actually closer to 6 than 5. It doesn't make any difference: that notation says to ignore anything to the right of the decimal point.

7. Originally Posted by JeffM
Look. We really want to help you. And some of us at various times in our career have done things with computers. But to answer a math question, we need to translate the practical problem into mathematical terms. You are probably giving us much more detail about the technical problem than we need, but not enough about the mathematical aspects of that problem

Okay, i'll try my hardest to explain what i'm seeing in my mind (since I don't really know how to state it mathematically.)

There exists between some fractions a chain of factors (I'm specifically only considering fractions that are just reciprocals of whole numbers, with a numerator of 1 and a whole number denominator 1/w)
whereby you can begin at one fraction and, so long as both of the fraction's denominators share some number of factors, follow the chain by dividing/multiplying by those shared factors to reach the other fraction.
The main point is that we're always working with a fraction that simplifies down to having a numerator of 1 (we're always working with a fraction of 1 full second).

For instance, let's get from 1/24 to 1/46 by following the factor chain.

1) 1/24 * 12 = 1/2 ;multiply by 12, a factor of 24
2) 1/2 ÷ 23 = 1/46 ;divide by 23 a factor of 46

I can tell now that the shortest distance in the factor chain between fractions that both have even denominators is always 2.

Next, i'll go from a fraction with an even denominator, to a fraction with an odd denominator. 1/36 to 1/105

1) 1/36 * 12 = 1/3 ;multiply by 12, a factor of 36
2) 1/3 ÷ 35 = 1/105 ;divide by 35, a factor of 105

The shortest distance here is 2 as well. This raises a new question. If both of the denominators can be connected with a factor chain, is the shortest distance always 2?
I really don't know.

Lastly, I want to go from 1/18 to 1/75 which is useful to me anyway. 18 and 75 share a factor 3

1) 1/18 * 6 = 1/3 ;multiply by 6, a factor of 18
2) 1/3 ÷ 25 = 1/75 ;divide by 25, a factor of 75

Okay, I think I see now. If the 2 numbers share a factor, you can always get from one fraction to another with a multiply and a divide. It's always two operations. That answers my question, I think.
I was caught up in the assumption that there might be an arbitrary number of operations (factors in the chain), but now I see it doesn't have to be a chain. I think it always simplifies down to just a single lowest common factor, or no common factors.

Now, I just need a way to programmatically determine the lowest common factor between 18 and any given number, if indeed they share a factor.

8. Well, given this knowledge, I now have the basic outline for a program that might work.

In my question I mentioned that I was passing to my code a simple multiplier, but now I see that I can pass it any arbitrary frame rate.
Let's say I pass it 60.

All I would need to do is divide 60 by all the factors of 18 (starting from 2) until I reach a factor that results in a remainder of 0. In this case the lowest factor to result in a remainder of 0 is obviously 2.
However, if given a different frame rate, and no such remainder of 0 is found, (it shares no factors) just increment the passed frame rate, and try again. (the number will now be even, and therefore the lowest factor will be 2)
Then, I would have to solve for x to figure out which factor of 18 when multiplied by 1/18 results in 1/2. (1/18 * x = 1/2). So, x = 9.
Now, i have to solve for y to figure out which factor of 60 results in 1/60 when 1/2 is divided by it (1/2 ÷ y = 1/60). So, y = 30.
Finally, I have to count the loops, multiply the number of loops by 9, and then divide it by 30.
n = loops per 18th of a second. n * 9 ÷ 30 = loops per 60th of a second.
Problem solved.

9. I do this all the time. I'll end up answering my own questions on forums, while trying to ask them.
I should probably put more effort into solving things on my own before asking for help.

10. Originally Posted by codyw1996
I do this all the time. I'll end up answering my own questions on forums, while trying to ask them.
I should probably put more effort into solving things on my own before asking for help.
Formulating questions carefully is frequently far more than half the battle when answering them.