HP Prime and TI-84 Plus CE: Binary Dot Product
Binary Dot Product
The binary, or inner product, of two binary integers is calculated by:
1. Using the AND operator on each bit.
2. Count the number of 1 bits from the result.
3. Take the result mod 2. The result will either by 0 (an even number of 1 bits) or 1 (an odd number of 1 bits).
Examples:
Binary dot product of 111011 and 100110.
111011
100110
From the left:
1st bit: 1 and 1 = 1
2nd bit: 1 and 0 = 0
3rd bit: 1 and 0 = 0
4th bit: 0 and 1 = 1
5th bit: 1 and 1 = 1
6th bit: 1 and 0 = 0
Number of 1 bits: 2
2 mod 2 = 0
Result: 111011 • 100110 = 0
Binary dot products are used in various applications, especially in quantum mechanics. Specific examples include the Bernstein-Vazirani Algorithm.
Program Notes
In order to compare the individual bits, the two binary integers are converted to strings. A loop is executed to compare string characters one by one.
The HP Prime has the BITAND function which compares each pairs of bits with the AND operation.
HP Prime Program: BINDOT
EXPORT DOTBIN(x,a)
BEGIN
// EWS 2023-05-13
// Bernstein-Vazirani
// x, a: binary integers
LOCAL f,m,i,s,c;
f:=BITAND(x,a);
// convert to strings
c:=CEILING(LOG(f)/LOG(2));
s:=STRING(f);
FOR i FROM 2 TO c+1 DO
IF MID(s,i,1)=="1" THEN
m:=m+1;
END;
END;
m:=m MOD 2;
RETURN m;
END;
TI-84 Plus CE Program: DOTBIN
"EWS 2023-05-11"
Disp "BINARY DOT PRODUCT"
Input "BINARY 1? ",Str1
Input "BINARY 2? ",Str2
length(Str1) → A
length(Str2) → B
If A ≠ B
Then
If A < B
Then
For(I, 1, B - A)
"0" + Str1 → Str1
End
Else
For(I, 1, A - B)
"0" + Str2 → Str2
End
End
End
ClrHome
Disp Str1, Str2
Pause
0 → M
For(I, 1, max(A,B))
If sub(Str1, I, 1)="1" and sub(Str2, I, 1)="1"
Then
M + 1 → M
End
End
remainder(M,2) → M
Disp M
Examples
Example 1: 1101 • 1001001 = 1
Example 2: 11100 • 11110 = 1
Example 3: 1011110 • 10101 = 0
Source
Biswas, Shrey. "The Bernstein-Vazirani Algorithm: Quantum Algorithms Untangled" Quantum Untangled. Medium. February 4, 2021. Retrieved May 12, 2023. https://medium.com/quantum-untangled/the-bernstein-vazirani-algorithm-quantum-algorithms-untangled-67e58d4a5096
Eddie
All original content copyright, © 2011-2023. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.
