• AVR Freaks

Hot!Is there a code-efficient "x % N" operation for 2^N?

Author
sjb741
Super Member
  • Total Posts : 805
  • Reward points : 0
  • Joined: 2010/01/25 08:45:39
  • Location: 0
  • Status: offline
2019/06/18 02:15:25 (permalink)
0

Is there a code-efficient "x % N" operation for 2^N?

I have a timer which ticks every mS. When a static variable 'Ticks' increments to a multiple of a constant P, event_P() fires. 
 
When 'Ticks' increments to a multiple of a Q, event_Q() fires.

Let P = N^2, Q = M^2 etc
Then 'uint16_t P' looks like this for example
 FEDCBA98 76543210
 00000000 10000000      //P
 00000001 00000000      //2*P
                        //3*p???
 00000010 00000000      //4*P
                        //5*P?
                        //6*P?
                        //7*P?
 00000100 00000000      //8*P                       
 
Is there a good way to test this so we see all multiples?
#1

11 Replies Related Threads

    Chris A
    Super Member
    • Total Posts : 842
    • Reward points : 0
    • Joined: 2010/07/20 04:37:07
    • Location: 0
    • Status: offline
    Re: Is there a code-efficient "x % N" operation for 2^N? 2019/06/18 02:37:24 (permalink)
    0
     !(P & (N-1)) until P overflows
     
    Unless I misunderstood you!
    #2
    pcbbc
    Super Member
    • Total Posts : 1381
    • Reward points : 0
    • Joined: 2014/03/27 07:04:41
    • Location: 0
    • Status: offline
    Re: Is there a code-efficient "x % N" operation for 2^N? 2019/06/18 03:27:09 (permalink)
    +1 (1)
    Does the OP really mean P = N^2, Q = M^2 ?
    i.e. Squares?!
     
    The thread title and example given seems to imply powers of 2, in which case a correct definition is P = 2^N, Q = 2^M
     
    In which case Chris A is correct.  Mask the incrementing timer with (2^x - 1).  If that value is zero, you have an exact multiple of 2^x.
     
    Worked example for x = 7:
    2^x = 128 = 00000000 10000000
    (2^x)-1 = 127 = 00000000 01111111
     
    FEDCBA98 76543210

    00000000 00000000 & 00000000 01111111 = 00000000 00000000 //0*P
    00000000 10000000 & 00000000 01111111 = 00000000 00000000 //1*P
    00000001 00000000 & 00000000 01111111 = 00000000 00000000 //2*P
    00000001 10000000 & 00000000 01111111 = 00000000 00000000 //3*P
    00000010 00000000 & 00000000 01111111 = 00000000 00000000 //4*P
    00000010 10000000 & 00000000 01111111 = 00000000 00000000 //5*P
    ....
    11111111 10000000 & 00000000 01111111 = 00000000 00000000 //511*P

     
    Edit: If you want to calculate (2^x) - 1 efficiently, use...
    (1 << x) - 1

    post edited by pcbbc - 2019/06/18 03:30:26
    #3
    LdB_ECM
    Senior Member
    • Total Posts : 159
    • Reward points : 0
    • Joined: 2019/04/16 22:01:25
    • Location: 0
    • Status: offline
    Re: Is there a code-efficient "x % N" operation for 2^N? 2019/06/18 03:46:03 (permalink)
    +1 (1)
    You use an Eulerloop on the clock, it is used by Windows and Linux clock subsystems and on graphics and splines because it allows you fixed precision without using floats.
     
    At the system at it's heart has a max value called unsurprisingly EulerMax
    Each entry into the system has a test value and a diff value
     
    So as a pseudocode example for timer1 which will be 37 ticks per second and timer2 to be 71 ticks per second and We have a clock that does 1000 ticks per second

    unsigned int Eulermax = 1000;
    //Setup timer 1
    unsigned int dt1 = 37;
    unsigned int t1 = EulerMax/2; // Traditional to start it half way but can be zero
    //Setup timer 2
    unsigned int dt2 = 71;
    unsigned int t2 = EulerMax/2; // Traditional to start it half way but can be zero
     
    // Each 1ms timer tick .. usually an interrupt
    t1 += dt1;
    if (t1 >= EulerMax)
    {
         // Time for a timer 1 tick
         t1 = t1 - EulerMax; // Subtract eulermax leaving remainder in t1
         // Execute a timer1 event
    }
    t2 += dt2;
    if (t2 >= EulerMax)
    {
         // Time for a timer 2 tick
         t2 = t2 - EulerMax; // Subtract eulermax leaving remainder in t2
         // Execute a timer2 event
    }

    If you follow what happens
    t1 will add 37, 1000 times so 37000 in 1 sec so it exceeds Eulermax 37 times (so 37 ticks per sec)
    t2 will add 71, 1000 times so 71000 in 1 sec so it exceeds Eulermax 71 times (so 71 ticks per sec)
     
    So its a way to get the nearest timer tick to the main clock with finite precision and no floats used.
    Your pulses will wobble plus or minus 1 count as per the rounding but you get exactly the number of ticks per second you asked.
     
    So it's a really simple code that has a wide variety of uses and something worth learning and I assume what you are trying to do. 
     
     
     
     
    post edited by LdB_ECM - 2019/06/18 03:50:55
    #4
    sjb741
    Super Member
    • Total Posts : 805
    • Reward points : 0
    • Joined: 2010/01/25 08:45:39
    • Location: 0
    • Status: offline
    Re: Is there a code-efficient "x % N" operation for 2^N? 2019/06/19 06:54:53 (permalink)
    0
    The EulerLoop code looks useful (and, incidentally kind of reminds of Bresenham's algorithm for some reason).
     
    I could have put my post better:
     
    Normally I'd use
       if(!(Ticks % P))
          Event_P();
    but this test is fairly 'expensive'.
     
    Therefore I was wanting to know if I could efficiently test for 1.P, 2.P, 3.P, 4.P, 5.P, 6.P... when P is (itself) a power of 2.
     
    Example:
    P = 4 = 2^2
    I want to fire an event every 4 ticks, so at 4,8,12,16,20 ticks...
     
    ...I think I've just seen an answer actually; it looks like I can compare the old Ticks with the new Ticks using XOR, then if (in this example) bit 2 of (oldTicks ^ Ticks) is '1', bit 2 has toggled, so that equates to an event every 4 ticks.
     
    Similar logic for, e.g., P = 4096 etc
     
    #define EVT_P  8
    void OnTick(void) //Typically this would be a timer ISR
    {
       static uint16_t oldTicks, Ticks=0;
       
       oldTicks = Ticks++;
       
       if((oldTicks ^ Ticks) & (1<<EVT_P))
       {
          printf("Ticks (%d) is a multiple of of %d\n", Ticks, (1<<EVT_P));
       }
    }//OnTick
     
    post edited by sjb741 - 2019/06/19 07:24:28
    #5
    1and0
    Access is Denied
    • Total Posts : 9982
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: Is there a code-efficient "x % N" operation for 2^N? 2019/06/19 07:14:14 (permalink)
    0
    if (Ticks - oldTicks == P) {
      oldTicks = Ticks;
      event_P();
    }

     
    #6
    sjb741
    Super Member
    • Total Posts : 805
    • Reward points : 0
    • Joined: 2010/01/25 08:45:39
    • Location: 0
    • Status: offline
    Re: Is there a code-efficient "x % N" operation for 2^N? 2019/06/19 07:27:20 (permalink)
    0
    Yes, also looks good. Whatever method is adopted it should easiliy cope with morethan one "if(!(x%N))" type condition, so multiple events are accomodated.
    #7
    1and0
    Access is Denied
    • Total Posts : 9982
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: Is there a code-efficient "x % N" operation for 2^N? 2019/06/19 07:31:24 (permalink)
    0
    if N is given, then you can do this
    if (Ticks - oldTicks == (1<<N)) {
      oldTicks = Ticks;
      event_P();
    }

    #8
    1and0
    Access is Denied
    • Total Posts : 9982
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: Is there a code-efficient "x % N" operation for 2^N? 2019/06/19 07:41:05 (permalink)
    0
    sjb741#define EVT_P 8
    void OnTick(void) //Typically this would be a timer ISR
    {
        static uint16_t oldTicks, Ticks=0;

        oldTicks = Ticks++;

        if((oldTicks ^ Ticks) & (1<<EVT_P))
        {
            printf("Ticks (%d) is a multiple of of %d\n", Ticks, (1<<EVT_P));
        }
    }//OnTick

    No need for oldTicks.  Try this
    #define EVT_P 8
    void OnTick(void) //Typically this would be a timer ISR
    {
      static uint16_t Ticks=0;

      if ( (Ticks & ((1<<EVT_P) - 1)) == 0 )
      {
        printf("Ticks (%d) is a multiple of of %d\n", Ticks, (1<<EVT_P));
      }
    }//OnTick

    post edited by 1and0 - 2019/06/19 07:45:30
    #9
    sjb741
    Super Member
    • Total Posts : 805
    • Reward points : 0
    • Joined: 2010/01/25 08:45:39
    • Location: 0
    • Status: offline
    Re: Is there a code-efficient "x % N" operation for 2^N? 2019/06/19 08:07:16 (permalink)
    0
    Good point Smile
    post edited by sjb741 - 2019/06/19 08:13:31
    #10
    NorthGuy
    Super Member
    • Total Posts : 5804
    • Reward points : 0
    • Joined: 2014/02/23 14:23:23
    • Location: Northern Canada
    • Status: offline
    Re: Is there a code-efficient "x % N" operation for 2^N? 2019/06/19 09:25:17 (permalink)
    0
    The easiest way is to use timer pre-scalers and post-scalers. This way you just get the timer interrupt 2^N times less frequently. Of course, you don't always get enough scale, but that's a different problem.
    #11
    1and0
    Access is Denied
    • Total Posts : 9982
    • Reward points : 0
    • Joined: 2007/05/06 12:03:20
    • Location: Harry's Gray Matter
    • Status: offline
    Re: Is there a code-efficient "x % N" operation for 2^N? 2019/06/19 09:34:55 (permalink)
    +1 (1)
    sjb741
    Normally I'd use
       if(!(Ticks % P))
          Event_P();
    but this test is fairly 'expensive'.
     

    For future reference, when P is a power of 2. That can be more efficiently implemented using bitwise AND:
     
       if(!(Ticks & (P - 1)))
          Event_P();
    #12
    Jump to:
    © 2019 APG vNext Commercial Version 4.5