• Advertisement

Archived

This topic is now archived and is closed to further replies.

difficult series ?

This topic is 5511 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi there, I wanna describe a formula for a series that happened to appear in my program but was unable to find a good one until now. The series looks like the following: Input (''x'') Output (''y'') x = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... y = 0 1 2 3 4 1 2 3 4 5 6 7 8 1 2 3 4 ... and so on. Any hint would be very appreciated. In the meanwhile I''m looking for my math book. Lorenz

Share this post


Link to post
Share on other sites
Advertisement
You''ll have to give us more than that. I''d say at LEAST three ''cycles''.

i.e.
0 1 2 3 4 -> 1st cycle
1 2 3 4 5 6 7 8 -> 2nd cycle

Share this post


Link to post
Share on other sites
Ok,Ok,


0 0
1 1
2 2
3 3
4 4
5 1
6 2
7 3
8 4
9 5
10 6
11 7
12 8
13 1
14 2
15 3
16 4
17 5
18 6
19 7
20 8
21 9
22 10
23 11
24 12
25 13
26 14
27 15
28 16
29 1
30 2
31 3
32 4
33 5
.. ..
60 32
61 1
................. and so on ...

There you go.

Share this post


Link to post
Share on other sites
I think the function to produce your series would look something like:

  
DWORD GetNum( DWORD x )
{
DWORD d = 4;
while( x / d )
{
x -= d;
d <<= 1;
}
return x;
}


Check it out and post back any questions u have

Share this post


Link to post
Share on other sites
The first thing you want to do when looking for a relationship is identify a pattern in the output, since the input is just sequencial from 0. From what I can see, excluding the first element, it starts at 1 then goes to 4. It then repeats from 1 and goes to 8, and next repeats from 1 to 16, 1 to 32. I'd say that the number it counts to is increasing by a power of two each iteration.

The hardest part now it coming up with a formula that maps your sequencial input to this pattern. The first step is to break down each iteration and try to look for relationships in the input, now that we have identified the output pattern:

1 1 5 1 13 1 29 17
2 2 6 2 14 2 30 18
3 3 7 3 15 3 .
4 4 8 4 16 4 etc.
9 5 17 5
10 6 18 6
11 7 19 7
12 8 20 8
21 9
22 10
23 11
24 12
25 13
26 14
27 15
28 16

I looked at it for about 15 minutes, and I couldn't come up with anything off the top of my head. It's hard to go backwards

[edited by - Zipster on January 21, 2003 5:18:17 AM]

Share this post


Link to post
Share on other sites

int yourValue(int x) {
int nextPowerOf2 = findNextPowerOf2(x);
return x - nextPowerOf2;
}


code for next power of two can be found on flipcode..

"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites
int fn(int x)
{
if (x == 0) return 0;
int y = x + 4;
return y - highestpowerof2LT(y);
}

''highestpowerof2LT'' is simply the highest power of 2 that is less than y. Some processors have a function to do this in a cycle or two. Otherwise you''ll need a lookup or loop, e.g.

int highestpowerof2LT(int y)
{
z = 1;
while (z < y) z <<= 1;
return z >> 1;
}

If you are generating a sequence you can avoid this loop by incrementing z whenever it is needed as the series advances.

Share this post


Link to post
Share on other sites
Just my usual caution against posting homework questions here. Not sure if this is one, since I know sprinter_trueno has been doing game related stuff, but please be clear what your purpose is and avoid asking homework questions.

Forum FAQ

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites

  • Advertisement