Lets Make Tech

# Circular Buffer Pointer Addition and Subtraction

This tutorial is to teach you how to add and subtract a value to a pointer value in a circular buffer without going over the size, or below 0, so that it loops back around. The goal is to do this without using any loops, negative numbers, or if statements. We just want a generic mathematical formula that can be used. We also want one formula that does both addition or subtraction depending on if you pass a positive or negative number.

Circular Buffer

As an example we will use one with a size of 8 (0-7). Lets call it var[buffersize] buffersize=7 Size=buffersize+1.

 7 6 5 4 3 2 1 0

Now to add or subtract to this we need to know a few things the size (S), the current pointer location (P), and the value we are adding or subtracting(X) and we will call the new value N.

We can't just say N=P-X or N=P+X. It works in some cases but in others it causes the value to exceed 7 or drop below 0, and we can't have that. We could use if statements and loops but that is slow.

If you want you can try to solve it yourself then check back and see if we came up with the same formula. If you come up with a better solution, let me know in the comments. Just remember, no negative numbers, 'if' statements, loops, and it must be compatible in across programming languages.

Here are some example values and their solutions:

S=8, P=5, and X=1

We know that 5+1=6 and 5-1=4. It stays inside the boundaries so it is ok.

Now lets try S=8, P=5, X=15. Now we have a problem, if you add 15 to 5 you exceed 7 and if you subtract 15 from 5 you drop below 0. This is bad, we want it to loop around. Count the tiles and loop back, you will find that adding you get 4 and subtracting you get 6.

So we are going to make one formula for addition, which is fairly easy to do, then another for subtraction which is not so easy.

I came up with N=(P+X)%S

Lets test it out on the previous examples.

1.S=8, P=5, and X=1

(5+1)%8=6%8=6.

2.S=8, P=5, X=15

(5+15)%8=20%8=4

The answers match up with what we found counting. Awesome, now for subtraction which is a little more tricky because we don't want to deal with any negative numbers.

Subtraction

Language Differences

So you may say alright subtraction must be N=(P-X)%S. Lets look at why N=(P-X)%S does not work in C based languages.

To understand this we have to understand the difference between "%" in C and "%" in other languages.

In C "%" is a remainder operator. The remainder will share the same sign as the division solution.

In other languages "%" is a modulo operator and will always give a positive result.

This causes -2%8 to either equal 2 or -6 depending on which language you are using.

You may notice that to get the correct answer with C, you just need to add that answer to the size and you will also get 2.

Solution

The formula I came up with is N=(S-(X%S)+P)%S

So lets test it out on those examples again.

1.S=8, P=5, and X=1

(8-(1%8)+P)%8=(8-1+5)%8=12%8=4

So far so good! Now to test one of cases that causes all the trouble.

2.S=8, P=5, X=15

(8-(15%8)+5)%8=(8-7+5)%8=6%8=6

It works! This should speed up your code if you have been using if statements or something like that previously.

Universal Formula

So if you want a formula that does both addition and subtraction so you can just pass a positive or negative value to a function.

((s*x*x)+(p + x)) % s

Formula List

S=buffer size, X=value being added (negative for subtraction), and P= the current pointer position.

N=(P+X)%S

Subtraction

Non C Languages Only:

N=(P+X)%S

C Languages Only:

N=(S+(P-X))%S

All Languages (Don't quote me on that, test to make sure)

N=(S-(X%S)+P)%S

Or if you prefer you can write it like this:

N=((S+P)-(X%S))%S

((s*x*x)+(p + x)) % s

Lets test it out with a sample program. I wrote this in c++ as a windows console app in visual studio.

In this program the value for each pointer is the same as the pointer. For example var=6, var=5. This is just to demonstrate that it is working correctly.

So here it is with the different equations

``````// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;
const int buffersize = 7;
int var[buffersize];
int p;
int s;
int quit;
void setup();
void loop();
void sub(int x);

int _tmain(int argc, _TCHAR* argv[])
{
while (1)
{
setup();//this gives each pointer the same value as its address. We will print it later.
loop();//test a bunch of values being added or subtracted to each pointer.
cout << "Enter \"0\" to quit:";
cin >> quit;
if (quit == 0)
{
return 0;
}
}
}

void setup()
{
s = buffersize + 1;
for (int i = 0; i < 7; i++)
{
var[i] = i;
}
}

void loop()
{
for (int i = 0; i < 7; i++)
{
p = i;
for (int j = 0; j < 21; j++)
{
sub(j);
}
}
}

{
cout << p << "+" << x << "=" <<(p + x) % s<<endl;
}

void sub(int x)
{
cout << p << "-" << x << "=" << (s - (x%s) + p) % s<<endl;
}``````

And here is the output

``````0+0=0
0-0=0
0+1=1
0-1=7
0+2=2
0-2=6
0+3=3
0-3=5
0+4=4
0-4=4
0+5=5
0-5=3
0+6=6
0-6=2
0+7=7
0-7=1
0+8=0
0-8=0
0+9=1
0-9=7
0+10=2
0-10=6
0+11=3
0-11=5
0+12=4
0-12=4
0+13=5
0-13=3
0+14=6
0-14=2
0+15=7
0-15=1
0+16=0
0-16=0
0+17=1
0-17=7
0+18=2
0-18=6
0+19=3
0-19=5
0+20=4
0-20=4
1+0=1
1-0=1
1+1=2
1-1=0
1+2=3
1-2=7
1+3=4
1-3=6
1+4=5
1-4=5
1+5=6
1-5=4
1+6=7
1-6=3
1+7=0
1-7=2
1+8=1
1-8=1
1+9=2
1-9=0
1+10=3
1-10=7
1+11=4
1-11=6
1+12=5
1-12=5
1+13=6
1-13=4
1+14=7
1-14=3
1+15=0
1-15=2
1+16=1
1-16=1
1+17=2
1-17=0
1+18=3
1-18=7
1+19=4
1-19=6
1+20=5
1-20=5
2+0=2
2-0=2
2+1=3
2-1=1
2+2=4
2-2=0
2+3=5
2-3=7
2+4=6
2-4=6
2+5=7
2-5=5
2+6=0
2-6=4
2+7=1
2-7=3
2+8=2
2-8=2
2+9=3
2-9=1
2+10=4
2-10=0
2+11=5
2-11=7
2+12=6
2-12=6
2+13=7
2-13=5
2+14=0
2-14=4
2+15=1
2-15=3
2+16=2
2-16=2
2+17=3
2-17=1
2+18=4
2-18=0
2+19=5
2-19=7
2+20=6
2-20=6
3+0=3
3-0=3
3+1=4
3-1=2
3+2=5
3-2=1
3+3=6
3-3=0
3+4=7
3-4=7
3+5=0
3-5=6
3+6=1
3-6=5
3+7=2
3-7=4
3+8=3
3-8=3
3+9=4
3-9=2
3+10=5
3-10=1
3+11=6
3-11=0
3+12=7
3-12=7
3+13=0
3-13=6
3+14=1
3-14=5
3+15=2
3-15=4
3+16=3
3-16=3
3+17=4
3-17=2
3+18=5
3-18=1
3+19=6
3-19=0
3+20=7
3-20=7
4+0=4
4-0=4
4+1=5
4-1=3
4+2=6
4-2=2
4+3=7
4-3=1
4+4=0
4-4=0
4+5=1
4-5=7
4+6=2
4-6=6
4+7=3
4-7=5
4+8=4
4-8=4
4+9=5
4-9=3
4+10=6
4-10=2
4+11=7
4-11=1
4+12=0
4-12=0
4+13=1
4-13=7
4+14=2
4-14=6
4+15=3
4-15=5
4+16=4
4-16=4
4+17=5
4-17=3
4+18=6
4-18=2
4+19=7
4-19=1
4+20=0
4-20=0
5+0=5
5-0=5
5+1=6
5-1=4
5+2=7
5-2=3
5+3=0
5-3=2
5+4=1
5-4=1
5+5=2
5-5=0
5+6=3
5-6=7
5+7=4
5-7=6
5+8=5
5-8=5
5+9=6
5-9=4
5+10=7
5-10=3
5+11=0
5-11=2
5+12=1
5-12=1
5+13=2
5-13=0
5+14=3
5-14=7
5+15=4
5-15=6
5+16=5
5-16=5
5+17=6
5-17=4
5+18=7
5-18=3
5+19=0
5-19=2
5+20=1
5-20=1
6+0=6
6-0=6
6+1=7
6-1=5
6+2=0
6-2=4
6+3=1
6-3=3
6+4=2
6-4=2
6+5=3
6-5=1
6+6=4
6-6=0
6+7=5
6-7=7
6+8=6
6-8=6
6+9=7
6-9=5
6+10=0
6-10=4
6+11=1
6-11=3
6+12=2
6-12=2
6+13=3
6-13=1
6+14=4
6-14=0
6+15=5
6-15=7
6+16=6
6-16=6
6+17=7
6-17=5
6+18=0
6-18=4
6+19=1
6-19=3
6+20=2
6-20=2
Enter "0" to quit:``````

And here it is with the universal formula

``````// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;
const int buffersize = 7;
int var[buffersize];
int p;
int s;
int quit;
void setup();
void loop();
void sub(int x);

int _tmain(int argc, _TCHAR* argv[])
{
while (1)
{
setup();//this gives each pointer the same value as its address. We will print it later.
loop();//test a bunch of values being added or subtracted to each pointer.
cout << "Enter \"0\" to quit:";
cin >> quit;
if (quit == 0)
{
return 0;
}
}
}

void setup()
{
s = buffersize + 1;
for (int i = 0; i < 7; i++)
{
var[i] = i;
}
}

void loop()
{
for (int i = 0; i < 7; i++)
{
p = i;
for (int j = 0; j < 20; j++)
{
sub(j);
}
}
}

{
cout << "Add" << s << "  Pointer:" << p << "+" << x << "=" << ((s*x*x) + (p + x)) % s << endl;
}

void sub(int x)
{
x = x*-1;
//cout <<"correct"<< p << "-" << x << "=" << (s - (x%s) + p) % s<<endl;
//cout << "Buffer Size:" << s << "  Pointer:" << p << "-" << x << "=" << ((s*x) + (p - x)) % s << endl;
//cout << "Test" << s << "  Pointer:" << p << "-" << x << "=" << ((s + p) - (x%s)) % s << endl;

cout << "Sub" << s << "  Pointer:" << p << "-" << x << "=" << ((s*x*x)+(p + x)) % s <<endl;

}``````

``````Add8  Pointer:0+0=0
Sub8  Pointer:00=0
Sub8  Pointer:0-1=7
Sub8  Pointer:0-2=6
Sub8  Pointer:0-3=5
Sub8  Pointer:0-4=4
Sub8  Pointer:0-5=3
Sub8  Pointer:0-6=2
Sub8  Pointer:0-7=1
Sub8  Pointer:0-8=0
Sub8  Pointer:0-9=7
Sub8  Pointer:0-10=6
Sub8  Pointer:0-11=5
Sub8  Pointer:0-12=4
Sub8  Pointer:0-13=3
Sub8  Pointer:0-14=2
Sub8  Pointer:0-15=1
Sub8  Pointer:0-16=0
Sub8  Pointer:0-17=7
Sub8  Pointer:0-18=6
Sub8  Pointer:0-19=5
Sub8  Pointer:10=1
Sub8  Pointer:1-1=0
Sub8  Pointer:1-2=7
Sub8  Pointer:1-3=6
Sub8  Pointer:1-4=5
Sub8  Pointer:1-5=4
Sub8  Pointer:1-6=3
Sub8  Pointer:1-7=2
Sub8  Pointer:1-8=1
Sub8  Pointer:1-9=0
Sub8  Pointer:1-10=7
Sub8  Pointer:1-11=6
Sub8  Pointer:1-12=5
Sub8  Pointer:1-13=4
Sub8  Pointer:1-14=3
Sub8  Pointer:1-15=2
Sub8  Pointer:1-16=1
Sub8  Pointer:1-17=0
Sub8  Pointer:1-18=7
Sub8  Pointer:1-19=6
Sub8  Pointer:20=2
Sub8  Pointer:2-1=1
Sub8  Pointer:2-2=0
Sub8  Pointer:2-3=7
Sub8  Pointer:2-4=6
Sub8  Pointer:2-5=5
Sub8  Pointer:2-6=4
Sub8  Pointer:2-7=3
Sub8  Pointer:2-8=2
Sub8  Pointer:2-9=1
Sub8  Pointer:2-10=0
Sub8  Pointer:2-11=7
Sub8  Pointer:2-12=6
Sub8  Pointer:2-13=5
Sub8  Pointer:2-14=4
Sub8  Pointer:2-15=3
Sub8  Pointer:2-16=2
Sub8  Pointer:2-17=1
Sub8  Pointer:2-18=0
Sub8  Pointer:2-19=7
Sub8  Pointer:30=3
Sub8  Pointer:3-1=2
Sub8  Pointer:3-2=1
Sub8  Pointer:3-3=0
Sub8  Pointer:3-4=7
Sub8  Pointer:3-5=6
Sub8  Pointer:3-6=5
Sub8  Pointer:3-7=4
Sub8  Pointer:3-8=3
Sub8  Pointer:3-9=2
Sub8  Pointer:3-10=1
Sub8  Pointer:3-11=0
Sub8  Pointer:3-12=7
Sub8  Pointer:3-13=6
Sub8  Pointer:3-14=5
Sub8  Pointer:3-15=4
Sub8  Pointer:3-16=3
Sub8  Pointer:3-17=2
Sub8  Pointer:3-18=1
Sub8  Pointer:3-19=0
Sub8  Pointer:40=4
Sub8  Pointer:4-1=3
Sub8  Pointer:4-2=2
Sub8  Pointer:4-3=1
Sub8  Pointer:4-4=0
Sub8  Pointer:4-5=7
Sub8  Pointer:4-6=6
Sub8  Pointer:4-7=5
Sub8  Pointer:4-8=4
Sub8  Pointer:4-9=3
Sub8  Pointer:4-10=2
Sub8  Pointer:4-11=1
Sub8  Pointer:4-12=0
Sub8  Pointer:4-13=7
Sub8  Pointer:4-14=6
Sub8  Pointer:4-15=5
Sub8  Pointer:4-16=4
Sub8  Pointer:4-17=3
Sub8  Pointer:4-18=2
Sub8  Pointer:4-19=1
Sub8  Pointer:50=5
Sub8  Pointer:5-1=4
Sub8  Pointer:5-2=3
Sub8  Pointer:5-3=2
Sub8  Pointer:5-4=1
Sub8  Pointer:5-5=0
Sub8  Pointer:5-6=7
Sub8  Pointer:5-7=6
Sub8  Pointer:5-8=5
Sub8  Pointer:5-9=4
Sub8  Pointer:5-10=3
Sub8  Pointer:5-11=2
Sub8  Pointer:5-12=1
Sub8  Pointer:5-13=0
Sub8  Pointer:5-14=7
Sub8  Pointer:5-15=6
Sub8  Pointer:5-16=5
Sub8  Pointer:5-17=4
Sub8  Pointer:5-18=3
Sub8  Pointer:5-19=2
Sub8  Pointer:60=6
Sub8  Pointer:6-1=5
Sub8  Pointer:6-2=4
Sub8  Pointer:6-3=3
Sub8  Pointer:6-4=2
Sub8  Pointer:6-5=1
Sub8  Pointer:6-6=0
Sub8  Pointer:6-7=7
Sub8  Pointer:6-8=6
Sub8  Pointer:6-9=5
Sub8  Pointer:6-10=4
Sub8  Pointer:6-11=3
Sub8  Pointer:6-12=2
Sub8  Pointer:6-13=1
Sub8  Pointer:6-14=0
Sub8  Pointer:6-15=7
Sub8  Pointer:6-16=6
Sub8  Pointer:6-17=5
Sub8  Pointer:6-18=4
Sub8  Pointer:6-19=3
Enter "0" to quit:``````

Alright, if you can think of a better formula that adds or subtracts a pointer value in a circular buffer let me know.

# Correlation Program

This program allows you to enter as many data sets as you like, then it finds the correlations between all of them.

Here is a sample output: Here is the code. This isn't a step by step tutorial, just a tutorial through example. If you have any question feel free to ask in the comments.

``````#include "stdafx.h"
#include <stdlib.h>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

const int size = 1000;
int variables;

void get_variables();
void get_data();
void completedataset();
void get_mean(int i);
void a(int i);
void asqr(int i);
void correlate();
float a_times_b_sum(int i, int j);

class DATASET{
public:
int id;
string name;
int size_of;
float data[size];
float mean;
float a[size];
float asqr[size];
float asqrsum;
};
DATASET dataset[size];

int _tmain(int argc, _TCHAR* argv[])
{
while (1)
{
get_variables();
get_data();
completedataset();
correlate();
}
return 0;
}

void get_variables()
{
string tempstring;
cout << "Number of variables: ";
cin >> tempstring;
if (!(istringstream(tempstring) >> variables).fail())
{

for (int i = 0; i < variables; i++)
{
cout << "Enter Variable " << i +1 << " Name:" << endl << ":";
cin >> dataset[i].name;
}
}
else
{
cout << "Invalid"<<endl;
}
}

void get_data()
{
bool next=false;
for (int i = 0; i < variables;i++)
{
dataset[i].size_of = 0;
next = false;
cout << "Variable: " << dataset[i].name<<endl;
cout << "Enter Data. Enter any letter to move to the next variable." << endl << ":";
for (int j = 0; next == false; j++)
{

{
cout << ":";
dataset[i].size_of++;
}
else
{
cout << "Moving Along..."<<endl;
next = true;
}
}
}
}

void completedataset()
{
for (int i = 0; i < variables; i++)
{
get_mean(i);
a(i);
asqr(i);
}
}

void get_mean(int i)
{
float sum = 0;
for (int j = 0; j < dataset[i].size_of; j++)
{
sum = sum + dataset[i].data[j];
}
dataset[i].mean = sum / (dataset[i].size_of);
}

void a(int i)
{
for (int j = 0; j < dataset[i].size_of;j++)
{
dataset[i].a[j] = dataset[i].data[j] - dataset[i].mean;
}
}

void asqr(int i)
{
dataset[i].asqrsum = 0;
for (int j = 0; j < dataset[i].size_of; j++)
{
dataset[i].asqr[j] = dataset[i].a[j] * dataset[i].a[j];
dataset[i].asqrsum = dataset[i].asqrsum + dataset[i].asqr[j];
}

}

void correlate()
{
float p;
for (int i = 0; i < variables; i++)
{
for (int j = 0; j < variables; j++)
{
p=(a_times_b_sum(i, j))/(sqrt(dataset[i].asqrsum*dataset[j].asqrsum));
cout << dataset[i].name << " & " << dataset[j].name << ": P=" << p<<endl;
}
}
}

float a_times_b_sum(int i , int j)
{
float sum=0;
for (int k = 0; k < dataset[i].size_of || k < dataset[j].size_of; k++)
{
sum = sum + (dataset[i].a[k] * dataset[j].a[k]);
}
return sum;
}``````

Home ← Older posts