• Forums
• Posts
Latest Posts
Active Posts
Recently Visited
Search Results
• Page Extras
• Forum Themes
• AVR Freaks

### Hot!Is there a code-efficient "x % N" operation for 2^N? Author
sjb741 Super Member • Total Posts : 846
• Reward points : 0
• Joined: 2010/01/25 08:45:39
• Location: 0
• Status: offline 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?

Chris A Super Member • Total Posts : 864
• 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!
pcbbc Super Member • Total Posts : 1703
• 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 7654321000000000 00000000 & 00000000 01111111 = 00000000 00000000 //0*P00000000 10000000 & 00000000 01111111 = 00000000 00000000 //1*P00000001 00000000 & 00000000 01111111 = 00000000 00000000 //2*P00000001 10000000 & 00000000 01111111 = 00000000 00000000 //3*P00000010 00000000 & 00000000 01111111 = 00000000 00000000 //4*P00000010 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
LdB_ECM Super Member • Total Posts : 456
• 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 1unsigned int dt1 = 37;unsigned int t1 = EulerMax/2; // Traditional to start it half way but can be zero//Setup timer 2unsigned int dt2 = 71;unsigned int t2 = EulerMax/2; // Traditional to start it half way but can be zero // Each 1ms timer tick .. usually an interruptt1 += 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}`

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
sjb741 Super Member • Total Posts : 846
• 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
1and0 Access is Denied • Total Posts : 11808
• 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();}`

sjb741 Super Member • Total Posts : 846
• 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.
1and0 Access is Denied • Total Posts : 11808
• 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();}`

1and0 Access is Denied • Total Posts : 11808
• 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 8void 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
sjb741 Super Member • Total Posts : 846
• 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 post edited by sjb741 - 2019/06/19 08:13:31
NorthGuy Super Member • Total Posts : 6486
• Reward points : 0
• Joined: 2014/02/23 14:23:23
• Status: offline Re: Is there a code-efficient "x % N" operation for 2^N? 2019/06/19 09:25:17 (permalink)
+1 (1)
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.
1and0 Access is Denied • Total Posts : 11808
• 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();
sjb741 Super Member • Total Posts : 846
• 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? 2020/04/04 05:56:48 (permalink)
0
XC8 2.10 Free version. Seems it does help (a lot) simply using powers of 2, so some optimisation is done
Summarise the coding styles
"% anything", "% (2^N)", "bit shift (2^N)"
as
"%9", "%8", "&(1<<8)"

Program memory usage in bytes
Optimisation = 0
975-->877-->867
Optimisation = 1
897-->813-->804

Empirically, you get a big gain in space efficiency simply using "Modulo 2^N", and then save a little more by replacing "%" with the bit shift method.

`#define EVT_P ((1<<8)-1)void OnTick(void) //Typically this would be a timer ISR{  static uint16_t Ticks=0;  Ticks++;   //if(!Ticks % 9) //Not a power of 2, poor space efficiency  //if(!Ticks % 8) //Much better space efficiency//Somewhat better again space efficiency using bit shift method   if(!(Ticks & EVT_P)) //True only if "All Zeroes" in bits EVT_P-1...0  {    printf("Ticks (%u = 0x%4X) is a multiple of of %u\n", Ticks, Ticks, (1+EVT_P));  }}//OnTick`

Note
FEDCBA98 76543210
00000000 10000000      //P = (1 << 7)
00000000 01111111      //P-1 = (1 << 7) - 1
--------------------------------------------
00000001 00000000      //2*P
00000001 10000000      //3*P
00000010 00000000      //4*P
00000010 10000000      //5*P
00001011 00000000      //6*P
00000100 00000000      //8*P
post edited by sjb741 - 2020/04/04 06:00:38
NorthGuy Super Member • Total Posts : 6486
• Reward points : 0
• Joined: 2014/02/23 14:23:23
• Status: offline Re: Is there a code-efficient "x % N" operation for 2^N? 2020/04/04 07:20:03 (permalink)
0
For 8-bit PICs, simple decrementing timer counts for each timer will be the most efficient.

`if (count-- == 0) {  count = period_value;  // process your event here}`

sjb741 Super Member • Total Posts : 846
• 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? 2020/04/06 01:20:45 (permalink)
0
Does that cope with multiple tests in the same ISR?

if(!Ticks % DEBOUNCE)
...
if(!Ticks % LONG_KEY_PRESS)
...
if(!Ticks % 500mS)
...
ric Super Member • Total Posts : 29542
• Reward points : 0
• Joined: 2003/11/07 12:41:26
• Location: Australia, Melbourne
• Status: online Re: Is there a code-efficient "x % N" operation for 2^N? 2020/04/06 01:35:46 (permalink)
+1 (1)
You would use one small variable for each required test.

I also post at: PicForum
Links to useful PIC information: http://picforum.ric323.co...opic.php?f=59&t=15
NEW USERS: Posting images, links and code - workaround for restrictions.
To get a useful answer, always state which PIC you are using! Jump to:
© 2021 APG vNext Commercial Version 4.5