Thread: number sequence fiddling

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    82

    number sequence fiddling

    Hi,

    Well the idea of bit fiddling or twiddling is pretty well established and there's a good deal of stuff out there on the web if you want to look it up.

    A similar (in spirit) activity can be done with the plain everyday number sequence 0,1,2,3 etc. and I wanted to know (if I describe it properly) what other people here might call it so I can google it and see if there are any recipes out there. By the way no branching (if's or ternary's) allowed.

    For example
    Code:
    int N=16;
    for(i=0;i<N;i++)
       printf("%i ",(i/4)%2);
    will get you 0,0,0,0,1,1,1,1,0,0,0,0 , a square wave alternatiing between 0 and 1 every 4 steps.
    I've been trying to get 0,1,1,1,0,-1,-1,-1,0,1 etc and have got
    Code:
    int N=16;
    for(i=0;i<N;i++)
       printf("%i ",1-2*(i/4)%2);
    but of course I need to get the zero coming up every power of 4 times. I'm sure this has been hacked out a number of times but don't quite know how to look it up.

    Suggestions welcome thank you for reading.
    Last edited by stabu; 03-03-2010 at 12:50 PM.

  2. #2
    Registered User lattica's Avatar
    Join Date
    Aug 2008
    Location
    Spacelike Hyperplane
    Posts
    16
    Quote Originally Posted by stabu View Post
    ... I need to get the zero coming up every power of 4 times ...
    Don't you mean every multiple of 4? If so, using the not operator will help you get those zeroes.

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Imagine taking this sequence:

    Seq_A = 0,0,0,0,1,1,1,1,...

    And subtracting 1 from each element. You get this:

    Seq_B = -1,-1,-1,-1,0,0,0,0,...

    Now add these sequences together to get:

    Seq_C = Seq_A + Seq_B = -1,-1,-1,-1,1,1,1,1,...

    Now, you want to knock out every fourth element, so invent another sequence:

    Seq_D = 0,1,1,1,0,1,1,1,...

    Multiply this with sequence C:

    Seq_E = Seq_C * Seq_D = 0,-1,-1,-1,0,1,1,1,...

    This is the sequence you want. No branching.

    (Well, I got the signs backwards, but you get it.)
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    0,1,1,1,0,1,1,1,0,1,1,1 is easy to do. First of all, the sequence that repeats is of length four, so the first thing we're going to have is a mod four. That'll give us a number from zero to three. Now we want to map zero to four and the rest to one.
    Code:
    f = (i%4+3)/4
    Another useful sequence here is 1,1,1,1,-1,-1,-1,-1,1,1,1,1
    Dividing by four and modding with two gives us zero or one depending whether we have an even or odd multiple of four. Subtracting twice that from one gives us the desired output
    Code:
    g = 1-((i/4)%2)*2
    All that's left is to combine these two.

    There are of course several other ways
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Mar 2008
    Posts
    82
    Many thanks
    lattica: for correcting to multiples of 4
    brewbuck for the prob decomposition
    iMalc for the restraint in not quite spoonfeeding me :-D

    OK .. so now I can generate my matrix-travelling-by-differential-index sequence func:
    Code:
    int DM=8;
    int f, g;
       i=0;
       while (i<32) {
           f = (i%DM+(DM-1))/DM;
           g = 1-((i/DM)%2)*2;
           printf("%2i ", f*g); 
           ++i;
       }
       printf("\n");
       i=0;
       while (i<32) {
           printf("%2i ", (1 - (i%DM)+DM-1)/DM);
           ++i;
       }
       printf("\n");
    This gets
    Code:
     0  1  1  1  1  1  1  1  0 -1 -1 -1 -1 -1 -1 -1  0  1  1  1  1  1  1  1  0 -1 -1 -1 -1 -1 -1 -1                                                              
     1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0
    so I move sideways first, reaching the end I pop down a row and move leftwards.
    The very first step is incorrect so I will jump that one. Obviously workable, but not hugely elegant.

    I think to get cuter code it would seem that there may be a bit fiddling recipe for this, but it's good for now.

    Many thanks you guys!

  6. #6
    Registered User
    Join Date
    Mar 2010
    Posts
    6
    stabu,
    I think the general term you want is "integer sequence." Wikipedia has an article that gives the names of a few dozen known examples. Try:
    Wikipedia:integer sequence
    Also:
    The On-Line Encyclopedia of Integer Sequences
    Given an integer sequence, find its name, and formula.
    The On-Line Encyclopedia of Integer Sequences

    In mathematics there is a huge amount of work involving rational sequences and series (the sum of a sequence of terms.)

    Gil
    Last edited by webmaster; 12-03-2012 at 01:36 AM. Reason: updated link

  7. #7
    Registered User
    Join Date
    Mar 2008
    Posts
    82
    Very nice, thanks gil_johnson.

    I had been getting close to this, I was running searches on "number sequences" but you're clearly right I should specify integer.


    Cheers!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. scanf oddities
    By robwhit in forum C Programming
    Replies: 5
    Last Post: 09-22-2007, 01:03 AM
  2. Number sequence help
    By Shakti in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 05-26-2005, 08:36 AM
  3. number sequence
    By valleyboy in forum C Programming
    Replies: 1
    Last Post: 05-01-2005, 02:24 PM
  4. Prime number program problem
    By Guti14 in forum C Programming
    Replies: 11
    Last Post: 08-06-2004, 04:25 AM
  5. Random Number problem in number guessing game...
    By -leech- in forum Windows Programming
    Replies: 8
    Last Post: 01-15-2002, 05:00 PM