Ken-Soft

Software and the World

  • 日本語
  • 한국어
  • 中文
  • italian
  • Portugese
  • Espanol
  • German

Base N to 10 Conversion Class - PHP (Base 62 Implementation)

Posted under PHP, Programming, Web Development by Kenny on Tuesday 31 August 2010 at 7:11 pm

Bookmark and Share

This class can be used convert a base N number into base 10, and back. (Which makes it ideal for usage in technologies such as URL shorteners.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

<?php
/**
 * BNID - Base N <=> 10 converter
 *
 * @author kenny cason
 * @site www.ken-soft.com
 */
class BNID {
        // Alphabet of Base N (This is a Base 62 Implementation)
        var $bN = array(
            '0','1','2','3','4','5','6','7','8','9',
            'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',
            'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'
        );
 
       // Alphabet of Base 86 (comment out the B62 array and comment this to try it out)
       /*var $bN = array(
            '0','1','2','3','4','5','6','7','8','9',
            'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',
            'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
	    '-','+','_','%','|','@','!','$','*','~','`','#','(',')','=','&','[',']','{','}','<','>',':',';'
        );*/
 
        var $baseN;
 
        function __construct() {
            $this->baseN = count($this->bN);
        }
 
        // convert base 10 to base N
        function base10ToN($b10num=0) {
            $bNnum = "";
            do {
                $bNnum = $this->bN[$b10num % $this->baseN] . $bNnum;
                $b10num /= $this->baseN;
            } while($b10num >= 1);     
            return $bNnum;
        }
 
        // convert base N to base 10
        function baseNTo10($bNnum = "") {
           $b10num = 0;
            $len = strlen($bNnum);
            for($i = 0; $i < $len; $i++) {
                $val = array_keys($this->bN, substr($bNnum, $i, 1));
                $b10num += $val[0] * pow($this->baseN, $len - $i - 1);
            }
            return $b10num;
        }
 
}
/*
// test, uncomment and call this script to demonstrate it's functionality
$conv = new BNID();
$max = pow($conv->baseN, 2);
for($i = 0; $i <= $max; $i++) {
    echo $conv->base10ToN($i).", ";
}
echo "<br/><br/>";
for($i = 0; $i <= $max; $i++) {
    $x = $conv->base10ToN($i);
    echo $conv->baseNTo10($x).", ";
}
*/
?>

If you want to use this as a URL shortener, below is a quick demo of how to use URL Rewrite to accept www.page.com/ and forward it to some page to process the ID (i.e. convert to base 10 ID and query a URL from the Database using the ID). The below implementation will work for a base 62 alphabet comprised of [0-9][A-Z][a-z], which is the demo I posted.
place the below text in .htaccess in your websites root directory

Options +FollowSymlinks
RewriteEngine on
RewriteBase /yourrootdirectory/
RewriteRule ^(([A-Z]*[a-z]*[0-9]*)*)$ main.php?b62id=$1 [L,QSA]

So it should take a domain www.abc.com, if you specify www.abc.com/zA4F, it would forward to www.abc.com/main.php?id=14576711
Here is a sample Demohttp://www.ken-soft.com/code/php/baseconvert/AABCz23

Share on Facebook

Ackermann–Péter function (2 arguments) - C/C++ - Recursive Implentation

Posted under C/C++, Mathematics by Kenny on Friday 16 July 2010 at 12:06 pm

Bookmark and Share

This is an implementation of the 2 argument version of the Ackermann Function (i.e. Ackermann-Péter function). In essence, this is an example of a very simple recursive function is an example of a total computable function that is not primitive recursive. Instead of making the internet even more redundant with unnecessary text, just click the above link to view the entire Wikipedia article.
Function’s like these are very fun to play with. I often think about the human brain and how it functions when I see these kinds of functions. Taking input from the environment and processing it, sometimes recursively (like in a thought cycle), then converging to some or many outputs.
C Implentation:
noteThis function grows extremely fast, such that it quickly out grows any primitive type in C, including the largest “unsigned long long” type. Though the program will likely crash with a 0xC0000005 error from too much recursion :)
It should run fine from A(0,0) to A(4,0) and likely crash while computing A(4,1), which is 65533. A(4,0) is 13, so the number of recursive calls jumps up enormously! I will be working on a custom, larger data type as well as a way around the error caused by too much recursion.

1
2
3
4
5
6
7
8
9
10
11
12

/**
 * Ackermann function - recursive implementation
 */
unsigned long long A(unsigned long long m, unsigned long long n) {
    if(m == 0) {
        return n + 1;
    }else if(n == 0) {
        return A(m - 1, 1);
    } else {
        return A(m - 1, A(m, n - 1));
    }
}

The entire source implentation can be found here
I obtained a list of some of the expected values from this site -> http://www-users.cs.york.ac.uk/susan/cyc/a/ackermnn.htm
Here are some of the values for 0 < m < 5, 0 < n < 6

n=0 n=1 n=2 n=3 n=4 n=5
m=0 1 2 3 4 5 6
m=1 2 3 4 5 6 7
m=2 3 5 7 9 11 13
m=3 5 13 29 61 125 253
m=4 13 65533 265536-3 2265536-3 A(3,2265536-3) A(3,A(4,4))

Some of the patterns formed are very amazing. For example: A(2, n), 0 <= n < infinite, will list odd numbers starting from 3 to infinite.
To demonstrate this just insert the below loop into your code:

1
2
3

for(int n = 0; n < 100; n++) {
      std::cout << "A(2, " << n << ") = " << A(2, n) << std::endl;
}
Share on Facebook

Simulation Program (Motivated John Conway’s Game of Life) - C/C++

Posted under C/C++, Programming, Security, Simulation by Kenny on Tuesday 13 July 2010 at 8:33 pm

Bookmark and Share

In this little simulation demo I created four simple rules, of which can be activated by uncommenting them out in the source code. Though nothing too complex emerges, I still liked some the resulting behavior.
Particularly, rule1(), results in colors slowly grouping together in various forms. It may be hard to immediately noticed so watch carefully. This was motivated by John Conway’s Game of Life.
The program was written in C/C++, all graphics are done using SDL
The whole source can be found here main.cpp
Compileg++ main.cpp -lSDL
Run./a.out

Game of Life Patterns Game of Life Patterns
Game of Life Patterns Game of Life Patterns

Rule1()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

for(int x = 0; x < worldWidth; x++) {
    for(int y = 0; y < worldHeight; y++) {
        int r = world[x][y].r;
        int g = world[x][y].g;
        int b = world[x][y].b;
        /*
          o o o
          o x o
          o o o
        */
        // RULES
        if(x > 0 && y > 0) { // top left
            if(world[x - 1][y - 1].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x - 1][y - 1].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x - 1][y - 1].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(y > 0) { // top
            if(world[x][y - 1].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x][y - 1].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x][y - 1].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(x < worldWidth - 1 && y > 0) { // top right
            if(world[x + 1][y - 1].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x + 1][y - 1].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x + 1][y - 1].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(x > 0) { //  left
            if(world[x - 1][y].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x - 1][y].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x - 1][y].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(x < worldWidth - 1) { // right
            if(world[x + 1][y].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x + 1][y].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x + 1][y].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(x > 0 && y < worldHeight - 1) { // bottom left
            if(world[x - 1][y + 1].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x - 1][y + 1].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x - 1][y + 1].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(y < worldHeight - 1) { // bottom
            if(world[x][y + 1].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x][y + 1].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x][y + 1].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(x < worldWidth - 1 && y < worldHeight - 1) { // bottom right
            if(world[x + 1][y + 1].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x + 1][y + 1].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x + 1][y + 1].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(r < 0) {
            r = 0;
        }
        if(g < 0) {
            g = 0;
        }
        if(b < 0) {
            b = 0;
        }
        if(r > 255) {
            r = 255;
        }
        if(g > 255) {
            g = 255;
        }
        if(b > 255) {
            b = 255;
        }
        world[x][y].r = r;
        world[x][y].g = g;
        world[x][y].b = b;
    }
}
Share on Facebook

Next Page »

Copyright © 2009 www.Ken-Soft.com