Warning: The colorful blinking lights are encoding sensitive information. ;)
I think in the world of Arduino a prime such as 999983 can be considered a large prime.
In this series of showing the power of a turing machine this whole week i spent building a prime generating machine.
To review, Turing Machine is the minimalistic machine that can solve any (interesting) problem.
If there is a way to do it, a Turing Machine will do it.
In other words most interesting problems have step by step procedure to solve them. The step by step procedure is called an algorithm. So if there is an algorithm then a Turing machine will solve it.
Our Arduino is a Turing Machine (Universal Turing Machine).
These are some ways i view Turing machines as. Turing machine is the ultimate machine. Turing machine is the father of all machines. Turing machine is the fullstop of machines. A turing machine can generate any machine. A turing machine can solve any problems. If you have a turing machine you dont need any other machine.
In the previous project we built a calculator using a Turing machine. This time a Turing machine transforms itself into a large prime generating machine.
I had 10 leds and 6 RGB leds in stock. I started by building this beast. It took 2 hours to complete it.
After that soon the constraints and limitations of arduino uno started hitting. First of all i realized the limited number of pins available.
There are only 12 pins for output. Pin 2-13.
Because of the pins limitation and red led can only have 2 states on and off i dismissed the above design. The above design turned out to be inefficient.
Instead of one red led using a RGB led turns out to be much efficient. It can generate many colors. If i use 16 different colors as 16 different states or digits then while 10 leds can represent 2^10 = 1024 numbers. Only three RGB led can represent 16 * 16 * 16 = 4096 numbers.
So i soon dismissed the idea of using normal leds. I checked my drawer and there lay exactly 6 RGB pins.
Upon further study of the UNO architecture.
I realized only 6 pins can be used for RGB leds to generate 16 different colors. You can see closely in the photo below that the pins that have a little ~ sign are pins that can do PWM meaning i can use analogwrite to write various different values. Other pins can only write 1 or 0.
Also i realized Anlong In pins can also be configured for output. Including the analog in pins we now have 12 + 6 = 18 pins that can be used for leds.
Since i had exactly 6 rgb leds and 18 pins available among which 6 pins can be used for PWM which helps generate 16 colors, it started feeling like the 6 RGB leds were waiting for this PRIME GENERATRING MACHINE project.
Each RGB led has 3 pins. We have total 6 leds which totals 6*3 = eacactly 18 pins i.e the number of pins available.
So the final design which i thought was more efficient is as follows. Ill use the top most two leds with PWM i.e the top most two leds will generate 16 colors each and the bottom 4 will generate 8 colors.
For the low leds since each led has 3 pins one for R, G and B and for each pin we can only write either 0 or 1 so we can generate 8 different colors.
If we write these values
R = 0 G = 0 B = 0 ->Off
R = 1 G = 0 B = 0 ->Red
R = 0 G = 1 B = 0 ->Green
R = 0 G = 0 B = 1 ->Blue
R = 1 G = 1 B = 0 ->Yellow
R = 1 G = 0 B = 1 ->Magenta
R = 0 G = 1 B = 1 ->Cyan
R = 1 G = 1 B = 1 ->White
For the top most two leds since we can use analogWrite we can write any value from 0 to 255. So we can generate many colors but we need distinguishing colors.
So i went with these colors
No night
low red
high red
low green
high green
low blue
high blue
low yellow
high yellow
low magenta
high magenta
low cyan
high cyan
low white
high white
Brown
The following video shows these 16 states of a RGB led
After deciding the design and the total number of states each led have i now have to come up with a new number system that this circuit or leds will use.
A number system is a way to represent numbers, understand them and do mathematics on them.
The number system we use is hindu arabic number system. It is just one way to represent numbers.
In binary system we use 0 and 1 to represent any number.
So we can create our own number system.
This is the number system i came up with. I named it the RGB Number System.
The place values are at the top. Each column lists all the symbols or digits available for that placevalue.
N, r, R are abbreviations for No light, low red, High red etc.
To the right are some examples of converting the hindu arabic number system numbers to the RGB number system.
Next i need to verify the correctness of this system. I wrote this javascript code to verify the correctness. I checked to make sure 1 million unique numbers can be represented with this system.
<script>
let placevalues = [65536, 4096, 512, 64, 8, 1];
let digitsHigh = ["N", "r", "R", "g", "G", "b", "B", "y", "Y", "c", "C", "m", "M", "w", "W", "O"];
let digitsLow = ["N", "R", "G", "B", "Y", "C", "M", "W"];
function getMultipliers(num){
let result = [];
let nonzeroadded = false;
for(let i=0; i<placevalues.length; i++){
if(placevalues[i] <= num){
let div = Math.floor(num / placevalues[i]);
result.push(div);
num = num - placevalues[i]*div;
nonzeroadded = true;
}
else{
if(nonzeroadded){
result.push(0);
}
}
}
return result;
}
function convertMultipliersToRGB(lis){
let numdigits = lis.length;
let result = "";
for(let i=0; i<numdigits; i++){
if(numdigits - i > 4){
result += digitsHigh[lis[i]];
}
else{
result += digitsLow[lis[i]];
}
}
return result;
}
let allNumbers = [];
for(let i=1; i<=1000000; i++){
allNumbers.push(convertMultipliersToRGB(getMultipliers(i)));
}
//If these two are same then there are no duplicates, we have 1 million unique representations
console.log(new Set(allNumbers).size);
console.log(allNumbers.length);
</script>
Here is the machine counting from 1 to ..... in RGB number system
After that creating prime generator is straight forward.
Here is the prime generating machine
Now came the optimization part.
I had learnt about an efficent way to find primes called the Sieve of Eratosthenes
My first attempt was to use this technique
So i wrote code to implment this method
Here is the code in C++
*************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <iostream>
using namespace std;
bool flags[1000000];
int main()
{
for(int i=0; i<1000000; i++){
flags[i] = false;
}
int nextPrime = 2;
cout << nextPrime << "\n";
while(true){
int count = 1;
while(nextPrime * count < 1000000){
flags[nextPrime * count] = true;
count += 1;
}
int temp = nextPrime;
while(flags[temp] == true){
temp += 1;
}
nextPrime = temp;
cout << nextPrime << "\n";
if(nextPrime > 1000000){
break;
}
}
return 0;
}
When it was time to implement it in arduino. Soon software limitation hit. Hardware limitation had hit earlier (low pins).
The software limitation was i couldnt create an array of bool flags[1000000];
Arduino only has 2k of RAM available which means 2000 bytes which meant at most i could create
bool flags[2000]
So i cannot use the sieve of Eratosthenes directly.
I came up with a modified version of sieve of Eratosthenes that only used bool flags[1000] 1000 bytes.
Here i test the correctness of this new algorithm
#include <iostream>
using namespace std;
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////HELPER FUNCTIONS//////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//slow prime tester
bool isPrime(long n){
for(long i=2; i<n; i++){
if(n % i == 0){
return false;
}
}
return true;
}
bool arr[1000];
//fast prime tester
bool isPrimeFast(long n){
if(n < 1000){
return arr[n];
}
bool isPrm = true;
for(int j=2; j<1000; j++){
if(arr[j]){
if(n % j == 0){
isPrm = false;
break;
}
}
}
return isPrm;
}
void fillPrimesTill1000(){
for(int i=0; i<1000; i++){
arr[i] = false;
}
for(int i=2; i<1000; i++){
if(isPrime(i)){
arr[i] = true;
}
}
}
int main()
{
fillPrimesTill1000();
//Find the primes from 3. No need to check even numbers.
for(long i=3; i<1000000; i +=2){
if(isPrimeFast(i) != isPrime(i)){ //uncomment this for fast version
//if(isPrime(i)){ //uncomment this for slow version
cout << i << " " << isPrimeFast(i) << " " << isPrime(i) << "\n";
break;
}
else{
cout << i << "PASS\n";
}
}
return 0;
}
You can notice with this optimization the speed gain is significant.
In less than 30 minutes the machine can find all primes till 1 million.
Here is the demonstration
Here is the complete arduino code. The circuit design is straightforward as shown in the video. 6 rgb leds to 18 pins in arduino.
//Place values for the RGB Number system
long placevalues[6] = {65536, 4096, 512, 64, 8, 1};
//Store the multipliers of the placevalues in this array
long result[6];
//pins for each RGB led. Each array inside the array is RGB pins.
int pins[6][3] = {{7, 4, 2}, {13, 12, 8}, {A0, A1, A2}, {A3, A4, A5}, {6, 5, 3}, {11, 10, 9}};
void setup() {
Serial.begin(9600);
//For fast prime function
fillPrimesTill1000();
}
void loop() {
//Find the primes from 3. No need to check even numbers.
for(long i=3; i<1000000; i +=2){
if(isPrimeFast(i)){ //uncomment this for fast version
//if(isPrime(i)){ //uncomment this for slow version
getMultipliers(i);
convertResultToRGB();
Serial.println(i);
}
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////HELPER FUNCTIONS//////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//slow prime tester
bool isPrime(long n){
for(long i=2; i<n; i++){
if(n % i == 0){
return false;
}
}
return true;
}
bool arr[1000];
//fast prime tester
bool isPrimeFast(long n){
if(n < 1000){
return arr[n];
}
bool isPrm = true;
for(int j=2; j<1000; j++){
if(arr[j]){
if(n % j == 0){
isPrm = false;
break;
}
}
}
return isPrm;
}
void fillPrimesTill1000(){
for(int i=0; i<1000; i++){
arr[i] = false;
}
for(int i=2; i<1000; i++){
if(isPrime(i)){
arr[i] = true;
}
}
}
//Get multipliers of the placevalues in RGB number system and stores the multipliers in the result array
void getMultipliers(long num){
bool nonzeroadded = false;
long index = 0;
for(long i=0; i<6; i++){
if(placevalues[i] <= num){
long div = num / placevalues[i];
result[index++] = div;
num = num - placevalues[i]*div;
nonzeroadded = true;
}
else{
result[index++] = 0;
}
}
}
void convertResultToRGB(){
writeLed(0, result[5]);
writeLed(1, result[4]);
writeLed(2, result[3]);
writeLed(3, result[2]);
writeLed(4, result[1]);
writeLed(5, result[0]);
}
void writeLed(int led, int d){
if(led <= 3){
if(d == 0){
//N
analogWrite(pins[led][0], 0);
analogWrite(pins[led][1], 0);
analogWrite(pins[led][2], 0);
}
else if(d == 1){
//R
analogWrite(pins[led][0], 255);
analogWrite(pins[led][1], 0);
analogWrite(pins[led][2], 0);
}
else if(d == 2){
//G
analogWrite(pins[led][0], 0);
analogWrite(pins[led][1], 255);
analogWrite(pins[led][2], 0);
}
else if(d == 3){
//B
analogWrite(pins[led][0], 0);
analogWrite(pins[led][1], 0);
analogWrite(pins[led][2], 255);
}
else if(d == 4){
//Y
analogWrite(pins[led][0], 255);
analogWrite(pins[led][1], 255);
analogWrite(pins[led][2], 0);
}
else if(d == 5)
{
//M
analogWrite(pins[led][0], 255);
analogWrite(pins[led][1], 0);
analogWrite(pins[led][2], 255);
}
else if(d == 6){
//C
analogWrite(pins[led][0], 0);
analogWrite(pins[led][1], 255);
analogWrite(pins[led][2], 255);
}
else if(d == 7){
//W
analogWrite(pins[led][0], 255);
analogWrite(pins[led][1], 255);
analogWrite(pins[led][2], 255);
}
}
else{
switch (d) {
case 0:
//do something when var equals 1
//N
analogWrite(pins[led][0], 0);
analogWrite(pins[led][1], 0);
analogWrite(pins[led][2], 0);
break;
case 1:
//r
analogWrite(pins[led][0], 50);
analogWrite(pins[led][1], 0);
analogWrite(pins[led][2], 0);
//do something when var equals 2
break;
case 2:
//R
analogWrite(pins[led][0], 255);
analogWrite(pins[led][1], 0);
analogWrite(pins[led][2], 0);
//do something when var equals 2
break;
case 3:
//g
analogWrite(pins[led][0], 0);
analogWrite(pins[led][1], 50);
analogWrite(pins[led][2], 0);
//do something when var equals 2
break;
case 4:
//G
analogWrite(pins[led][0], 0);
analogWrite(pins[led][1], 255);
analogWrite(pins[led][2], 0);
//do something when var equals 2
break;
case 5:
//b
analogWrite(pins[led][0], 0);
analogWrite(pins[led][1], 0);
analogWrite(pins[led][2], 50);
//do something when var equals 2
break;
case 6:
//B
analogWrite(pins[led][0], 0);
analogWrite(pins[led][1], 0);
analogWrite(pins[led][2], 255);
//do something when var equals 2
break;
case 7:
//y
analogWrite(pins[led][0], 50);
analogWrite(pins[led][1], 50);
analogWrite(pins[led][2], 0);
//do something when var equals 2
break;
case 8:
//Y
analogWrite(pins[led][0], 255);
analogWrite(pins[led][1], 255);
analogWrite(pins[led][2], 0);
//do something when var equals 2
break;
case 9:
//m
analogWrite(pins[led][0], 50);
analogWrite(pins[led][1], 0);
analogWrite(pins[led][2], 50);
//do something when var equals 2
break;
case 10:
//M
analogWrite(pins[led][0], 255);
analogWrite(pins[led][1], 0);
analogWrite(pins[led][2], 255);
//do something when var equals 2
break;
case 11:
//c
analogWrite(pins[led][0], 0);
analogWrite(pins[led][1], 50);
analogWrite(pins[led][2], 50);
//do something when var equals 2
break;
case 12:
//C
analogWrite(pins[led][0], 0);
analogWrite(pins[led][1], 255);
analogWrite(pins[led][2], 255);
//do something when var equals 2
break;
case 13:
//w
analogWrite(pins[led][0], 50);
analogWrite(pins[led][1], 50);
analogWrite(pins[led][2], 50);
//do something when var equals 2
break;
case 14:
//W
analogWrite(pins[led][0], 255);
analogWrite(pins[led][1], 255);
analogWrite(pins[led][2], 255);
//do something when var equals 2
break;
case 15:
//O
analogWrite(pins[led][0], 200);
analogWrite(pins[led][1], 20);
analogWrite(pins[led][2], 0);
//do something when var equals 2
break;
default:
// if nothing else matches, do the default
// default is optional
break;
}
}
}
What is engineering but solving problems under constraints.
SOME PRIMES
G B N C
512*2 + 64*1 + 8*0 + 1*3 = 1091
G R R R
512*2 + 64*1 + 8*1 + 1*1 = 1097
G G G B
512*2 + 64*2 + 8*2 + 1*3 = 1171
G B N R
512*2 + 64*2 + 8*0 + 1*1 = 1153
G C N R
512*2 + 64*6 + 8*0 + 1*1 = 1409
Other primes can be generated by taking screenshots from the videos.
No comments:
Post a Comment