Sunday, June 12, 2011
Russian Peasant Method of multiplication
Russian peasant method is one of the method I have used for multiplication of Integers over the years on processors that don't have explicit multiplication Instructions. Russian peasant method suits well because you just need instructions to double the number and halve the number, which is basically shift left and shift right respectively for a binary number. Almost all microprocessor will have these instructions and C language provides these operators << and >> respectively.
Step 1. If the multiplier is odd, add the multiplicand to the result. The red rows.
Step 2. Double the multiplicand.
Step 3. Halve the multiplier.
Step 4. Repeat step 1 to 3 till multiplier is zero.
You can switch the role of multiplicand and multiplier because of multiplication's commutative nature, doing so will reduce the number of iterations needed.
Here is the C code.
How it's done?
It is easy to explain the process with a diagram. Here it illustrates the multiplication of 5 x 4. Step 1. If the multiplier is odd, add the multiplicand to the result. The red rows.
Step 2. Double the multiplicand.
Step 3. Halve the multiplier.
Step 4. Repeat step 1 to 3 till multiplier is zero.
You can switch the role of multiplicand and multiplier because of multiplication's commutative nature, doing so will reduce the number of iterations needed.
Here is the C code.
#includelong multiply(int ml, int mp) { long result =0; while( mp != 0) { if( mp & 01) /* if odd add ml to result */ { result += ml; } ml <<= 1; mp >>= 1; } return result; } int main(void) { int x = 7; int y = 7; printf("%ld\n", multiply(x,y)); return 0; }
Labels: Embedded
Wednesday, May 25, 2011
Palindrome Puzzle
I heard this puzzle on car talk. It's about finding odometer reading which is a palindrome. The twist is that a 6 digit odometer read's palindrome in the morning when Tommy left to work and the odometer read palindrome again when Tommy came back home!
The complete detail is on Tommy's Drive to Work
To solve this problem
1. Find all 6 digit palindrome heuristically.
2. Sort all the palindrome in ascending order.
3. Compare adjacent palindromes, if they are less than 100(miles) print the palindrome.
Here is my c++ solution
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> // 5/25/2011 5:39 PM // Car talk Puzzle 6 digit palindrome// Shankar Chakkere // http://www.cartalk.com/content/puzzler/transcripts/201121/index.html std::vector <unsigned int > palindrome;bool sortVector (unsigned int i,unsigned int j) { return (i < j);} int main() { // for 6 digit (654321) palindrome // digits 1 and 6 are same, 2 & 5 are same, 3 & 4 are same // e.g 175571 // Generate all possible palindrome heuristically for(int x = 0; x <= 9; x++) { for(int y =0; y <= 9; y++) { for(int z =0; z <= 9; z++) { // Have not tried to optimize for sake of clarity unsigned int pal = x*100000 + y*10000 + z*1000 + z*100 + y*10 + x; palindrome.push_back(pal); } } } // // Sort them in ascending order std::sort(palindrome.begin(), palindrome.end(), sortVector); std::vector<unsigned int>::iterator it = palindrome.begin(); unsigned int previous = *it++; while(it != palindrome.end()) { unsigned int current = *it++; // if the diffence of adjacent odometer reading is less than 100 miles // assuming he does not drives more than 100 miles if( (current - previous) < 100) { std::cout << std::setw(6) << std::setfill('0') << previous << " " << current << " miles driven= " << current - previous << std::endl; } previous = current; } return 0; }The Output
099990 100001 miles driven= 11
199991 200002 miles driven= 11
299992 300003 miles driven= 11
399993 400004 miles driven= 11
499994 500005 miles driven= 11
599995 600006 miles driven= 11
699996 700007 miles driven= 11
799997 800008 miles driven= 11
899998 900009 miles driven= 11Labels: Puzzles
Monday, December 13, 2010
Code Brainstorm
Imagine you get a brainstorm to a pressing software problem. You jot it down on a sheet of paper and you have itch to test it. You have a computer but don't have have the proper tools to test it.
If you have access to internet you can use one of many online IDE with multiple language support to test it.
To test and save source code snippets, I use ideone.com, but there are many like codepad.org for e.g.
The advantages are:
If you have access to internet you can use one of many online IDE with multiple language support to test it.
To test and save source code snippets, I use ideone.com, but there are many like codepad.org for e.g.
The advantages are:
- Multiple language support.
- Save your source code snippets.
- Share the source code.
- Download the source code etc.
- Start on one Computer and finish it on other Computer
- You can code from iPad!
Labels: Programming
Sunday, November 23, 2008
Anagram
Anagram is re-arranging the letters in the word such that it gives a different meaning word. Eg. syrup and pyres.
The problem is to find all the anagrams in the english dictionary. The best solution I found is in the Jon Bentley's book Programming Pearls book.
Here is the algorithm:
Step 1 : Arrange each words in the dictionary in an order(Alphabetic), this gives the signature of the word.
Step 2 : Then sort these signature along with the word.
Step 3 : The words with the same signature are the anagrams.
words | signature( The word sorted in Alphabetical order) | signature with words, | Anagram, words with same signature |
pal | alp | alp pal | |
lap | alp | alp lap | pal lap |
cat | act | act cat |
We will use the unix philosophy for solving this problem .
Unix philosophy states:
Write programs that do one thing and do it well. Write programs to work together. Write programs to handle text streams, because that is a universal interface.
We will write a c++ program to generate the signature and the word pair, use the unix sort program to sort the signatures and use AWK script to extract the words with the same signature. The resulting words are the anagrams.
#include <iostream>#include <fstream>#include <string>#include <iterator>#include <algorithm>bool charComp (char i, char j)
{return (i < j);
}
int main (int argc, char * const argv[])
{std::string signature;
std::ifstream file;
std::istream_iterator<std::string> inputItr;
if(argc > 1)
{file.open(argv[1]);
inputItr = std::istream_iterator<std::string>(file);
} else {inputItr = std::istream_iterator<std::string>(std::cin);
}for (; inputItr != std::istream_iterator<std::string>(); inputItr++)
{ signature = *inputItr; // Sort the word in alphabetical orderstd::sort(signature.begin(), signature.end(), charComp);
// Print the signature of the word and the wordstd::cout << signature << " " << *inputItr << std::endl;
}return 0;
}
The program reads the words as the string either from file or through the standard input. Then sorts each word alphabetically which makes the signature of the word and prints the signature and the word.
The sort program will sort the output of the program. It arranges the words with same signature next to each other. The command looks like this:
~ Shankar$ cat /usr/share/dict/words |tr [A-Z] [a-z]| ./Anagram |sort
Here cat is feeding the words in the dictionary to the anagram program. The words are all converted to lower case before feeding by tr. The anagram program will print the signature of each word along with the word onto standard output like this:
aaaabcilllz calabazilla
aaaabcl alcaaba
aaaabcllmnrtu antambulacral
The AWK filter program prints the words with the same signature on a line.
#!/usr/bin/awk -f
# Shankar Chakkere (shankara_c@yahoo.com)
# Given the input of the form
# signature word
#
# prsu spur
# prsuu usurp
# prsuy pursy
# prsuy pyrus
# prsuy syrup
# prsuyy syrupy
# .......
# print all the words which has the same signature
# pursy pyrus syrup
# which are anagrams.
function saveState(state)
{ prevSignature = $1; prevWord = $2; matched = state;}
{ if (NR == 1) { saveState(0); } else { # for all the lines greater than 1 # print the previous word if its signature had matched if($1 == prevSignature) { printf("%s ",prevWord); saveState(1); } else { # print the previous word if its signature had matched. # This is the last word of the anagram list, so print line feed if(matched == 1) printf("%s\n ",prevWord); saveState(0); } }}
Tying them all together:
~ Shankar$ cat /usr/share/dict/words |tr [A-Z] [a-z]| ./Anagram |sort |./printAnagram.awk
Will print the list of anagrams on to the standard output.
Labels: c++
Counting Bits
There are many reasons we need to count the number of bits set in a data. It can be used to calculate the parity of a byte. To find the hamming distance etc.There are many ways to do it in C / C++.
Method 1
int countBits(unsigned int x){int i=0;while(x != 0){if(x & 0x1){++i;}x >>= 1;}return i;}
How it works?
Unlike the assembly language C or C++ don't have a operator to test if the bit is set. Here we mask the rest of the bits except the least significant bit and test if it is zero or not. It is guaranteed to work for unsigned number because the C++ standard guarantees it.
Shift operators
The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.
What it means is , when you shift right, the most significant bit is padded with zero as show in the diagram below.
Disadvantage:
For the worst case when least significant and the most significant bits are set eg. 10000001.
Method 2
This method is an exercise in Kernighan and Ritchie's "The C programming Language" book.
int countBits(unsigned int x){ int i=0;
while (x != 0) { ++i; x &= x - 1; // deletes the rightmost bit that is set in x } return i;}
How it works?This method uses the property of subtracting a binary number with one. When its done the least significant bit set will be reset.
For decimal 3 which is 011 in binary, the following diagram illustrates the process.011 value & 010 value -1 count = 1 ------ 010 010 value & 001 value -1 count = 2 ------ 000As we see the bit set count is 2.
Advantage:
The number of loops depends on the number of bits set, even for the worst case eg. 10000001 it does it in two loops.
Method 3
Using lookup table. This speeds the operation because we are doing a nibble (4 bits ) at a time instead of a bit at a time.
const int int2bitCount[16] ={0,1,1,2,1,2,2,3,1,2,3,3,2,3,4,4};int countBits(unsigned int x){int count = 0;while(x != 0){count += int2bitCount[ x & 0xf ];x >>= 4;}return count;}
How it works?
The lookup table stores the number of bits that are set for its index. Here we are creating a lookup table for a nibble. 4 bits at a time seems to be a best compromise for space / time. We are also assuming that the integer is a multiple of 4 bits.
Advantage:
The number of loops for the worst case is sizeof( int ) / 4.
This is how you invoke it.
#include <iostream>
int main(int argc, char* argv[])
{
unsigned int x = 0xfffe;
std::cout << std::hex << x << " has " << std::dec << countBits(x) << " bits" << std::endl;
return 0;
}
Labels: c++
Tuesday, May 13, 2008
Creating a binary test file
Some time you need a binary file with known contents to test your communication software.
Here is a quick way to generate one using Gawk. Gawk is GNU AWK.
Creates a binary file which contains value from 0 to 0xff.
You can extend this to generate a PROM/ROM lookup table like for example a sine table for an 8 bit table.
Here is a quick way to generate one using Gawk. Gawk is GNU AWK.
/cygdrive/c/develop> gawk 'BEGIN {x=0; while(++x<=255){printf "%02x ",x;}; exit}' |xxd -r -p >numtable.bin
Creates a binary file which contains value from 0 to 0xff.
/cygdrive/c/develop> od -t x1 numtable.bin
0000000 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10
0000020 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f 20
0000040 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2f 30
0000060 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3f 40
0000100 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f 50
0000120 51 52 53 54 55 56 57 58 59 5a 5b 5c 5d 5e 5f 60
0000140 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 70
0000160 71 72 73 74 75 76 77 78 79 7a 7b 7c 7d 7e 7f 80
0000200 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f 90
0000220 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f a0
0000240 a1 a2 a3 a4 a5 a6 a7 a8 a9 aa ab ac ad ae af b0
0000260 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf c0
0000300 c1 c2 c3 c4 c5 c6 c7 c8 c9 ca cb cc cd ce cf d0
0000320 d1 d2 d3 d4 d5 d6 d7 d8 d9 da db dc dd de df e0
0000340 e1 e2 e3 e4 e5 e6 e7 e8 e9 ea eb ec ed ee ef f0
0000360 f1 f2 f3 f4 f5 f6 f7 f8 f9 fa fb fc fd fe ff
0000377
You can extend this to generate a PROM/ROM lookup table like for example a sine table for an 8 bit table.
/cygdrive/c/develop> gawk 'BEGIN {x=0;pi=3.14; while(++x<=90){printf "%02d ",sin(pi/180*x)*100;}; exit}'
Labels: Utilities
Saturday, February 10, 2007
Encrypting a file.
It is difficult to keep track of all the passwords. I used to write passwords in Kannada ,my language, hoping that not many can read. Now I save all my passwords using KeePass on Windows and KeePassX on Mac OS X. It keeps the entire password in a database and locks it with one master password. The database is compatible across the platform, and the same database can be used on Windows or Mac OS X.
The problem:
Imagine you are on the road, you can't recall the password for a certain web site.
Here is the solution:
Save a password database as text file and encrypt that file.
Step 1. In keeppass File -> Export To -> CSV File (Under Windows, Or as Text in Mac OS X).
Save it as say Database.kdb.csv. Copy this file onto your thumbdrive.
Step 2. Compiling a multiplatform file encrytion program bcrypt.
In Windows(cygwin):
Download the source and unpack into a directory.
Copy bcrypt.exe and cygwin1.dll onto your thumb drive
In Mac OS X:
Unzip the source file.
You can also run make install if you want it to be available for other users on your system.
Testing it:
Plug the thumbdrive
Using it on the road:
Step 3. So now you can use your password on the road even on the machines which does not have bcrypt installed (because you have the executable for Windows and Mac OS X and the encrypted password file on the thumb drive).
The problem:
Imagine you are on the road, you can't recall the password for a certain web site.
Here is the solution:
Save a password database as text file and encrypt that file.
Step 1. In keeppass File -> Export To -> CSV File (Under Windows, Or as Text in Mac OS X).
Save it as say Database.kdb.csv. Copy this file onto your thumbdrive.
Step 2. Compiling a multiplatform file encrytion program bcrypt.
In Windows(cygwin):
Download the source and unpack into a directory.
schakkere@shankar ~To encrypt a file on your thumb drive.
$ cd develop/bcrypt/
/ecos-c/usr/shankar/develop/bcrypt
schakkere@shankar ~/develop/bcrypt
$ make
gcc -O2 -Wall -c main.c
gcc -O2 -Wall -c blowfish.c
gcc -O2 -Wall -c rwfile.c
rwfile.c: In function `deletefile':
rwfile.c:123: warning: implicit declaration of function `initstate'
gcc -O2 -Wall -c keys.c
gcc -O2 -Wall -c wrapbf.c
gcc -O2 -Wall -c endian.c
gcc -O2 -Wall -c wrapzl.c
gcc -O2 -Wall -o bcrypt main.o blowfish.o rwfile.o keys.o wrapbf.o endian.o wrapzl.o -L/usr/local/lib -lz
Info: resolving _optind by linking to __imp__optind (auto-import)
Info: resolving _optarg by linking to __imp__optarg (auto-import)
schakkere@shankar ~/develop/bcrypt
$ make install
mkdir -p /usr/local/bin;\
mkdir -p /usr/local/man/man1;\
cp bcrypt /usr/local/bin;\
cp bcrypt.1 /usr/local/man/man1;\
chmod 755 /usr/local/bin/bcrypt;\
chmod 644 /usr/local/man/man1/bcrypt.1
schakkere@shankar ~/develop/bcrypt
$ which bcrypt
/usr/local/bin/bcrypt
schakkere@shankar ~/develop/bcrypt
$ bcrypt
Usage is: bcrypt -[orc][-sN] file1 file2..
-o Write output to standard out
-r Do NOT remove input files after processing
-c Do NOT compress files before encryption
-sN How many times to overwrite input files with random data
schakkere@shankar ~/develop/bcryptOption -s5 overwrites the original file 5 times with random data before deleting it.
$ cd /cygdrive/E/backup/keepass/
schakkere@shankar /cygdrive/E/backup/keepass
$ ls
Database.kdb Database.kdb.csv
schakkere@shankar /cygdrive/E/backup/keepass
$ bcrypt -s5 Database.kdb.csv
Encryption key:Key must be at least 8 characters
Encryption key:
Again:
schakkere@shankar /cygdrive/E/backup/keepass
$ ls -al
drwxr-xr-x 2 schakkere mkgroup-l-d 0 Feb 7 00:21 .
drwxr-xr-x 11 schakkere mkgroup-l-d 0 Feb 7 00:20 ..
-rw-r--r-- 1 schakkere mkgroup-l-d 13084 Jan 10 12:23 Database.kdb
-rw-r--r-- 1 schakkere mkgroup-l-d 2126 Feb 15 22:11 Database.kdb.csv.bfe
Copy bcrypt.exe and cygwin1.dll onto your thumb drive
In Mac OS X:
Unzip the source file.
Shankar-Chakkeres-Computer:~/develop/bcrypt shankar$ makeCopy bcrypt to ~/bin and onto your thumb drive.
You can also run make install if you want it to be available for other users on your system.
Testing it:
Plug the thumbdrive
Shankar-Chakkeres-Computer:~/develop/bcrypt shankar$ ~/bin/bcrypt -r -o /Volumes/6JAN2007/backup/keepass/Database.kdb.csv.bfe | grep -i bankIt works!
Encryption key:
"Bank of America","xxx","xxx","xxx","xxx"
Using it on the road:
Step 3. So now you can use your password on the road even on the machines which does not have bcrypt installed (because you have the executable for Windows and Mac OS X and the encrypted password file on the thumb drive).
Labels: HOWTO, OS X, Utilities
