algorithm to split number into two pieces

[Jay]

Hey Guys,

I need an algorithm/formula to do the following:

I have two 32-bit timers cascaded to form a 64-bit timer, max value
per timer(50sec). This is the way they work:

value | timer1 | timer2
5 50 3
when timer1 counts down to zero, timer2 would count down to two.
Timer1 would reload the value 50 and start counting down, this goes on
till timer2 reaches zero.

I need to be able to load them most efficiently. So, pseudo-code looks
like this??

if (value < max_value)
load timer1 = value;
load timer2 = 1;
if (value == even number) && (value < max_value*2)
load timer1 = value/2;
load timer2 = 2;
For a list of different values:

value | timer1 | timer2
10 | 10 | 1
50 | 50 | 1 (max_value)
60 | 30 | 2
80 | 40 | 2
100 | 50 | 2 (max_value*2)
110 | 11 |10
Now the fun starts, since I cannot load timer1 with a value more than
50, I have to split the value 110 so that timer1 would have the
maximum value possible. Some more scenarios,
120 | 30 | 4
150 | 50 | 3
160 | 40 | 4
I just can't see a pattern to implement an algorithm. Any help will be
greatly appreciated.

 

[xarax]

Hey Guys,

I need an algorithm/formula to do the following:

I have two 32-bit timers cascaded to form a 64-bit timer, max value
per timer(50sec). This is the way they work:

value | timer1 | timer2
5 50 3
when timer1 counts down to zero, timer2 would count down to two.
Timer1 would reload the value 50 and start counting down, this goes on
till timer2 reaches zero.

I need to be able to load them most efficiently. So, pseudo-code looks
like this??

if (value < max_value)
load timer1 = value;
load timer2 = 1;
if (value == even number) && (value < max_value*2)
load timer1 = value/2;
load timer2 = 2;
For a list of different values:

value | timer1 | timer2
10 | 10 | 1
50 | 50 | 1 (max_value)
60 | 30 | 2
80 | 40 | 2
100 | 50 | 2 (max_value*2)
110 | 11 |10
Now the fun starts, since I cannot load timer1 with a value more than
50, I have to split the value 110 so that timer1 would have the
maximum value possible. Some more scenarios,
120 | 30 | 4
150 | 50 | 3
160 | 40 | 4
I just can't see a pattern to implement an algorithm. Any help will be
greatly appreciated.

What does this have to do with C?

Looks like the pattern you want is to have
a loop index that starts at 50 and counts down
to 1. Each pass of the loop calculates the
remainder from dividing the "value" by the
loop index. When you find a remainder of
zero, the loop index is your timer1 value.
The quotient is your timer2.

In your example above, the value=120 would
yield timer1=40, timer2=3.

However, since your timer1 and timer2 cannot
exceed 50, the theoretical highest "value" is
50*50. I believe there may be some prime numbers
less than 2500 that will fail this algorithm.



--
----------------------------
Jeffrey D. Smith
Farsight Systems Corporation
24 BURLINGTON DRIVE
LONGMONT, CO 80501-6906
http://www.farsight-systems.com
z/Debug debugs your Systems/C programs running on IBM z/OS!
Are ISV upgrade fees too high? Check our custom product development!

 

[Leor Zolman]

Hey Guys,

I need an algorithm/formula to do the following:

I have two 32-bit timers cascaded to form a 64-bit timer, max value
per timer(50sec). This is the way they work:

value | timer1 | timer2
5 50 3
when timer1 counts down to zero, timer2 would count down to two.
Timer1 would reload the value 50 and start counting down, this goes on
till timer2 reaches zero.

I need to be able to load them most efficiently. So, pseudo-code looks
like this??

if (value < max_value)
load timer1 = value;
load timer2 = 1;
if (value == even number) && (value < max_value*2)
load timer1 = value/2;
load timer2 = 2;
For a list of different values:

value | timer1 | timer2
10 | 10 | 1
50 | 50 | 1 (max_value)
60 | 30 | 2
80 | 40 | 2
100 | 50 | 2 (max_value*2)
110 | 11 |10
Now the fun starts, since I cannot load timer1 with a value more than
50, I have to split the value 110 so that timer1 would have the
maximum value possible. Some more scenarios,
120 | 30 | 4
150 | 50 | 3
160 | 40 | 4
I just can't see a pattern to implement an algorithm. Any help will be
greatly appreciated.

Is there some correlation between setting timer1 to the "maximum value
possible" and loading both timers "most efficiently"? If so, I don't get
what that correlation is, so I'm going to ignore the "maximum value
possible" part for timer1. With that requirement eliminated, here's
something that seems to get the job done for your given values of "value"
and max_value:

#include <stdio.h>

void setTimers(int value, int max_value, int *timer1p, int *timer2p)
{
*timer1p = value % max_value;
*timer2p = 1 + value / (max_value - 1);
if (*timer1p == 0) /* there may be a more elegant way */
{ /* to do this, but I'm being lazy */
*timer1p = max_value;
--*timer2p;
}
}

int main(void)
{
int i, timer1, timer2;
int values[] = {10, 50, 60, 80, 100, 110, 120, 150, 160};
const int size = sizeof values / sizeof *values;
const int max_value = 50;

for (i = 0; i < size; i++)
{
setTimers(values, max_value, &timer1, &timer2);
printf("for value = %d (max_value = %d): "
"timer1 = %d, timer2 = %d\n",
values, max_value, timer1, timer2);
}
return 0;
}

Running this yields:

for value = 10 (max_value = 50): timer1 = 10, timer2 = 1
for value = 50 (max_value = 50): timer1 = 50, timer2 = 1
for value = 60 (max_value = 50): timer1 = 10, timer2 = 2
for value = 80 (max_value = 50): timer1 = 30, timer2 = 2
for value = 100 (max_value = 50): timer1 = 50, timer2 = 2
for value = 110 (max_value = 50): timer1 = 10, timer2 = 3
for value = 120 (max_value = 50): timer1 = 20, timer2 = 3
for value = 150 (max_value = 50): timer1 = 50, timer2 = 3
for value = 160 (max_value = 50): timer1 = 10, timer2 = 4

That help?
-leor

Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html

 

[nrk]

Hey Guys,

I need an algorithm/formula to do the following:

I have two 32-bit timers cascaded to form a 64-bit timer, max value
per timer(50sec). This is the way they work:

value | timer1 | timer2
5 50 3
when timer1 counts down to zero, timer2 would count down to two.
Timer1 would reload the value 50 and start counting down, this goes on
till timer2 reaches zero.

I need to be able to load them most efficiently. So, pseudo-code looks
like this??

if (value < max_value)
load timer1 = value;
load timer2 = 1;
if (value == even number) && (value < max_value*2)
load timer1 = value/2;
load timer2 = 2;
For a list of different values:

value | timer1 | timer2
10 | 10 | 1
50 | 50 | 1 (max_value)
60 | 30 | 2
80 | 40 | 2
100 | 50 | 2 (max_value*2)
110 | 11 |10
Now the fun starts, since I cannot load timer1 with a value more than
50, I have to split the value 110 so that timer1 would have the
maximum value possible. Some more scenarios,
120 | 30 | 4
150 | 50 | 3
160 | 40 | 4
I just can't see a pattern to implement an algorithm. Any help will be
greatly appreciated.

I am not sure if I understood it correctly, but if I did, note that your two
counters together cannot count prime numbers greater than 50 or if the
prime factors cannot be broken into two products <= 50 (Since they can only
count a multiple of some prime number <= 50). One way to go about it is to
factor your input value into prime factors, then multiply them one by one
till you hit the value closest to 50. That would be the value of timer1
and the product of the remaining factors would be timer2. Here's code that
demonstrates this (having hard-coded the primes from 1..50). The code's
arranged so that value1 gets the maximum possible value and value2 is the
rest of the factors multiplied together. If a number cannot be represented
as value1 * value2 then it returns -1. Based on your input constraints
(only even numbers etc.) you should be able to optimize this further:

#include <stdio.h>

#define MAX_VALUE1 50
#define MAX_VALUE2 50

static short primes[] =
{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, };

int split_value(int value, int *value1, int *value2, int *factors) {
int nfacts = 0;
int temp = value;
int i;

if ( temp == 1 ) {
*value1 = 1;
*value2 = 1;
return 0;
}

i = 0;
while ( i < sizeof primes/sizeof primes[0] &&
temp != 1 ) {
while ( temp != 1 && temp % primes == 0 ) {
factors[nfacts++] = primes;
temp /= primes;
}
++i;
}

if ( temp != 1 )
return -1; /* This value cannot be represented
in two counters <= 50 */
*value1 = 1, *value2 = 1;
i = 0;

for ( i = nfacts - 1; i >= 0; --i ) {
if ( *value1 * factors <= MAX_VALUE1 ) {
*value1 *= factors;
factors = -1;
}
}

for ( i = 0; i < nfacts; ++i )
if ( factors > 1 )
*value2 *= factors;

if ( *value2 > MAX_VALUE1 )
return -1; /* This value cannot be represented
in two counters <= 50 */

return 0;
}

int main(void) {
int i, j;
int v1, v2;
int factors[sizeof primes/sizeof primes[0]];

printf("\tValue\t|\tTimer1\t|\tTimer2\n");
for ( i = 1; i <= 2500; ++i ) {
#ifdef PRINT_ALL
printf("\t%5d\t", i);
#endif
for ( j = 0; j < sizeof factors/sizeof factors[0]; ++j )
factors[j] = -1;
if ( split_value(i, &v1, &v2, factors) == 0 ) {
#ifndef PRINT_ALL
printf("\t%5d\t", i);
#endif
printf("|\t%6d\t|\t%6d\n", v1, v2);
}
#ifdef PRINT_ALL
else {
printf("Not Possible { ");
for ( j = 0; factors[j] != -1; ++j )
printf("%d, ", factors[j]);
printf(" }\n");
}
#endif
}

return 0;
}

-nrk.

 

[nrk]

Hey Guys,

I need an algorithm/formula to do the following:

I have two 32-bit timers cascaded to form a 64-bit timer, max value
per timer(50sec). This is the way they work:

value | timer1 | timer2
5 50 3
when timer1 counts down to zero, timer2 would count down to two.
Timer1 would reload the value 50 and start counting down, this goes on
till timer2 reaches zero.

I need to be able to load them most efficiently. So, pseudo-code looks
like this??

if (value < max_value)
load timer1 = value;
load timer2 = 1;
if (value == even number) && (value < max_value*2)
load timer1 = value/2;
load timer2 = 2;
For a list of different values:

value | timer1 | timer2
10 | 10 | 1
50 | 50 | 1 (max_value)
60 | 30 | 2
80 | 40 | 2
100 | 50 | 2 (max_value*2)
110 | 11 |10
Now the fun starts, since I cannot load timer1 with a value more than
50, I have to split the value 110 so that timer1 would have the
maximum value possible. Some more scenarios,
120 | 30 | 4
150 | 50 | 3
160 | 40 | 4
I just can't see a pattern to implement an algorithm. Any help will be
greatly appreciated.

I am not sure if I understood it correctly, but if I did, note that your
two counters together cannot count prime numbers greater than 50 or if the
prime factors cannot be broken into two products <= 50 (Since they can
only
count a multiple of some prime number <= 50). One way to go about it is
to factor your input value into prime factors, then multiply them one by
one
till you hit the value closest to 50. That would be the value of timer1
and the product of the remaining factors would be timer2. Here's code
that
demonstrates this (having hard-coded the primes from 1..50). The code's
arranged so that value1 gets the maximum possible value and value2 is the
rest of the factors multiplied together. If a number cannot be
represented
as value1 * value2 then it returns -1. Based on your input constraints
(only even numbers etc.) you should be able to optimize this further:

#include <stdio.h>

#define MAX_VALUE1 50
#define MAX_VALUE2 50

static short primes[] =
{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, };

int split_value(int value, int *value1, int *value2, int *factors) {
int nfacts = 0;
int temp = value;
int i;

if ( temp == 1 ) {
*value1 = 1;
*value2 = 1;
return 0;
}

i = 0;
while ( i < sizeof primes/sizeof primes[0] &&
temp != 1 ) {
while ( temp != 1 && temp % primes == 0 ) {
factors[nfacts++] = primes;
temp /= primes;
}
++i;
}

if ( temp != 1 )
return -1; /* This value cannot be represented
in two counters <= 50 */
*value1 = 1, *value2 = 1;
i = 0;

for ( i = nfacts - 1; i >= 0; --i ) {
if ( *value1 * factors <= MAX_VALUE1 ) {
*value1 *= factors;
factors = -1;
}
}

for ( i = 0; i < nfacts; ++i )
if ( factors > 1 )
*value2 *= factors;

if ( *value2 > MAX_VALUE1 )
return -1; /* This value cannot be represented
in two counters <= 50 */

AARGH!! If you *really* want value1 to be >= value2, you would have to do a
compare and exchange here. I thought I had it nailed, but turns out if you
have a prime factor (like 39) that's large enough it buggers up that logic.
So, here's the fix if you definitely want value1 >= value2:
if ( *value1 < *value2 )
temp = *value2, *value2 = *value1, *value1 = temp;

-nrk.

return 0;
}

int main(void) {
int i, j;
int v1, v2;
int factors[sizeof primes/sizeof primes[0]];

printf("\tValue\t|\tTimer1\t|\tTimer2\n");
for ( i = 1; i <= 2500; ++i ) {
#ifdef PRINT_ALL
printf("\t%5d\t", i);
#endif
for ( j = 0; j < sizeof factors/sizeof factors[0]; ++j )
factors[j] = -1;
if ( split_value(i, &v1, &v2, factors) == 0 ) {
#ifndef PRINT_ALL
printf("\t%5d\t", i);
#endif
printf("|\t%6d\t|\t%6d\n", v1, v2);
}
#ifdef PRINT_ALL
else {
printf("Not Possible { ");
for ( j = 0; factors[j] != -1; ++j )
printf("%d, ", factors[j]);
printf(" }\n");
}
#endif
}

return 0;
}

-nrk.

 

[nrk]

Hey Guys,

I need an algorithm/formula to do the following:

I have two 32-bit timers cascaded to form a 64-bit timer, max value
per timer(50sec). This is the way they work:

value | timer1 | timer2
5 50 3
when timer1 counts down to zero, timer2 would count down to two.
Timer1 would reload the value 50 and start counting down, this goes on
till timer2 reaches zero.

I need to be able to load them most efficiently. So, pseudo-code looks
like this??

if (value < max_value)
load timer1 = value;
load timer2 = 1;
if (value == even number) && (value < max_value*2)
load timer1 = value/2;
load timer2 = 2;
For a list of different values:

value | timer1 | timer2
10 | 10 | 1
50 | 50 | 1 (max_value)
60 | 30 | 2
80 | 40 | 2
100 | 50 | 2 (max_value*2)
110 | 11 |10
Now the fun starts, since I cannot load timer1 with a value more than
50, I have to split the value 110 so that timer1 would have the
maximum value possible. Some more scenarios,
120 | 30 | 4
150 | 50 | 3
160 | 40 | 4
I just can't see a pattern to implement an algorithm. Any help will be
greatly appreciated.

I just noticed that all your values are multiples of 10. If you're only
looking at multiples of 10 the following will do the trick (no need for
prime factorization):

#define MAX_VALUE1 50
#define MAX_VALUE2 50

int split_value(int value, int *value1, int *value2) {
int i;

for ( i = MAX_VALUE1; i > 0; i -= 5 ) {
if ( value % i == 0 ) {
*value2 = value/i;
if ( *value2 > MAX_VALUE2 )
return -1;
*value1 = i;
if ( *value1 < *value2 )
i = *value1, *value1 = *value2, *value2 = i;
return 0;
}
}

return -1;
}

-nrk.

 

[David Resnick]

Hey Guys,

I need an algorithm/formula to do the following:

I have two 32-bit timers cascaded to form a 64-bit timer, max value
per timer(50sec). This is the way they work:

value | timer1 | timer2
5 50 3
when timer1 counts down to zero, timer2 would count down to two.
Timer1 would reload the value 50 and start counting down, this goes on
till timer2 reaches zero.

I need to be able to load them most efficiently. So, pseudo-code looks
like this??

if (value < max_value)
load timer1 = value;
load timer2 = 1;
if (value == even number) && (value < max_value*2)
load timer1 = value/2;
load timer2 = 2;
For a list of different values:

value | timer1 | timer2
10 | 10 | 1
50 | 50 | 1 (max_value)
60 | 30 | 2
80 | 40 | 2
100 | 50 | 2 (max_value*2)
110 | 11 |10
Now the fun starts, since I cannot load timer1 with a value more than
50, I have to split the value 110 so that timer1 would have the
maximum value possible. Some more scenarios,
120 | 30 | 4
150 | 50 | 3
160 | 40 | 4
I just can't see a pattern to implement an algorithm. Any help will be
greatly appreciated.

This isn't really a "C" question, but is rather a more general
question about algorithms. As such, you might get more help in
comp.programming. Just a thought.

My 2 cents:

If all values you are using are multiples of 10 (true for all your
examples), you can get up to 500 by doing
timer1 = 10;
timer2 = value/10;

That appears to cover all your examples. Presumably it is more
complex than that though? If you can have arbitrary values, well,
this is trickier. You could figure out the prime factors of the
number and try to combine them into two values that are each < 50
(is that really the requirement?). But there will be numbers for
which that is not possible

If you are able to alter the meaning of the timers, it seems like
a better use would be to have timer2 be the number of 50 second
periods and timer1 be the remainder, as in

timer1 = value%50;
timer2 = value/50;

Hope that is in some way helpful...

-David

 

[David Rubin]

Hey Guys,

I need an algorithm/formula to do the following:

I have two 32-bit timers cascaded to form a 64-bit timer, max value
per timer(50sec). This is the way they work:

value | timer1 | timer2
5 50 3
when timer1 counts down to zero, timer2 would count down to two.
Timer1 would reload the value 50 and start counting down, this goes on
till timer2 reaches zero.

I think in this example, you mean for value to be 150, no?

[snip]

For a list of different values:

value | timer1 | timer2
10 | 10 | 1
50 | 50 | 1 (max_value)
60 | 30 | 2
80 | 40 | 2
100 | 50 | 2 (max_value*2)
110 | 11 |10
Now the fun starts, since I cannot load timer1 with a value more than
50, I have to split the value 110 so that timer1 would have the
maximum value possible.

It looks to me like timer2 is not really a timer, but a count of how many
iterations you need to make in timer1. Why don't you do this:

for a given value v

timer2 = v / 50;
timer1 = v % 50;
if(timer1 == 0 and timer2 > 0){
timer1 += 50;
timer2 -= 1;
}

This way you end up with the following table:

v t1 t2
10 10 0
50 50 0
60 10 1
80 30 1
100 50 1
110 10 2

When t1 and t2 are both zero, the timer is expired.

/david

 

[Jay]

On 23 Feb 2004 14:56:44 -0800, (e-mail address removed) (Jay)
wrote:

Is there some correlation between setting timer1 to the "maximum value
possible" and loading both timers "most efficiently"?

What happens is, when timer1 expires it generates an interrupt that
triggers timer2 to count down. I just wanted to generate the least
number of interrupts by loading timer1 with maximum value possible.
example: the number 20 could be loaded in as follows:

timer1 | timer2
20 1 (would generate only 1 interrupt)
10 2
5 4
1 20 (would generate 20 interrupts)

}

 

[Leor Zolman]

What happens is, when timer1 expires it generates an interrupt that
triggers timer2 to count down. I just wanted to generate the least
number of interrupts by loading timer1 with maximum value possible.
example: the number 20 could be loaded in as follows:

timer1 | timer2
20 1 (would generate only 1 interrupt)
10 2
5 4
1 20 (would generate 20 interrupts)

}

I originally had the impression that the "max_value" could be independent
of the initial value you put into timer1 (i.e., you have a max_value and a
"value", and then you want to compute optimal values for timer1 and
timer2). But it looks more as if you're saying that timer1 has a "memory"
of its initial value, and it can only go back to that particular value
after it expires? Sorry, this is too arbitrary for me... I'll just let the
embedded folks (to which this hopefully makes some sort of sense) handle
it... ;-)
-leor
Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html

 

[Nick Landsberg]

This whole thread probably belongs in comp.algorithms
since it's not C-specific... but at the bottom
you will find a suggestion.

I originally had the impression that the "max_value" could be independent
of the initial value you put into timer1 (i.e., you have a max_value and a
"value", and then you want to compute optimal values for timer1 and
timer2). But it looks more as if you're saying that timer1 has a "memory"
of its initial value, and it can only go back to that particular value
after it expires? Sorry, this is too arbitrary for me... I'll just let the
embedded folks (to which this hopefully makes some sort of sense) handle
it... ;-)
-leor
Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html

Suggestion:

The problem seems to be to find factors of the required
number such that the largest factor does not exceed 50.

(If the required value is less than 50, the problem
is trivially handled with an "if" statement.)

The constraint is that once timer1 is set, it cannot
be reset to a different value. (Correct?)

Assuming the numbers are not huge, one could intelligently
iterate down by two's from 50 (or 49 if the number is odd)
until one got down below the square root of the
input value. (Or iterate UP from the square root
of the input value until 50 was exceeded, if that
suits you better). Use integer divide and modulo
to determine if there is a remainder.

If any matches were found before the loop
terminates, use the larger of the two values for timer1 and the
smaller for timer2. If no matches were found, as would be
the case for a prime number, e.g. 53, you would be SOL
and have to load 1 into timer1 and 53 into timer2.
Again, a special case easily handled.

(53 is a prime, isn't it?)

 

[Nick Landsberg]

In a previous post Nick Landsberg had a brain-fart and wrote:

(See the correction below about the algorithm, my apologies
but that's what happens when you try to babysit your
grandkids and think at the same time)

This whole thread probably belongs in comp.algorithms
since it's not C-specific... but at the bottom
you will find a suggestion.





Suggestion:

The problem seems to be to find factors of the required
number such that the largest factor does not exceed 50.

(If the required value is less than 50, the problem
is trivially handled with an "if" statement.)

The constraint is that once timer1 is set, it cannot
be reset to a different value. (Correct?)

Assuming the numbers are not huge, one could intelligently
iterate down by two's from 50 (or 49 if the number is odd)
until one got down below the square root of the
input value. (Or iterate UP from the square root
of the input value until 50 was exceeded, if that
suits you better). Use integer divide and modulo
to determine if there is a remainder.

On second thought, it is more efficient to start at
2 or 3 (even or odd) and increment by 2's until
you hit the square-root. Even more efficient
looping parameters could be used if this
becomes a problem. Sorry about the braindamaged
looping construct up there.