Miner's Outpost: January 2014

Friday, January 31, 2014

The Bounty (Conclusion)

In our first article we covered how to translate the single bit logical XOR (exclusive OR) function into its arithmetic equivalent. In part 2 we discussed how to step through the individual bits of a multiple bit operand so that we could transform our original XOR function into a bitwise operation. Lastly, in this article we will combine all of the information we've discussed so far in the previous two articles and synthesize it into the very programs that I submitted as my entries for the original challenge.

BEFORE WE BEGIN

Although I am fluent in a few computer languages, my quick and dirty language of choice is Perl. For those interested in porting this example to other languages, the code should run equally well under Python with minor edits. Furthermore, although this particular challenge called for an implementation of the XOR function, the principles used to translate the function into its arithmetic equivalent apply equally toward the translation of other logical functions. In all such cases, the utility of the number (-1) will usually prove to be indispensable whether used to implement the logical function itself, or used as an alternate modulo 2 substitute.

PUTTING IT ALL TOGETHER

At this point we have investigated all of the elements that we'll use to complete our program. We have developed arithmetic equivalents for our XOR function. We have implemented ways to step through each bit of our operands to perform bitwise operations. In short, we have assembled all of the ingredients; now it is time to bake this cake!

As you might imagine, despite our new understanding of the challenge, this program will be somewhat complicated to describe with plenty of room for typos. For this reason, I we'll actually be employing the computer itself to generate the final equation. Perl is well suited for this purpose although I suspect that Python would be an equally valid choice.

Given input variables $a and $b, we begin by breaking down each operand into its bitwise constitutents:

#!/usr/bin/perl

# our improvised %2 function: ((1-(-1)**$n)/2)

for ($i=0; $i<32; $i++) # 32 bits

{

$hash= sprintf("%02x", $i);

$ai= "a".$hash; #hash for var containing rotate eq a.bit[i]

$bi= "b".$hash; #hash for var containing rotate eq b.bit[i]

    $n= "\$a*2**(32-$i)%(2**32-1)"; # rotate to bit a.bit[i]
    $var{$ai}= "((1-(-1)**($n))/2)"; # assign hash for a.bit[i]
    $n= "\$b*2**(32-$i)%(2**32-1)"; # rotate to bit b.bit[i]
    $var{$bi}= "((1-(-1)**($n))/2)"; # assign hash for b.bit[i]

}

The above code will cycle through the 32 bits (0-31) of both operands and assign each hash in %var to be the equation necessary (given an input '$a' or input '$b' ) to rotate the bit at the position specified by $i to the one's position (2^0) and to evaluate the result as either being even (0) or odd(0).

First the code creates a hash using the name of the operand ('a' or 'b') concatenated to the hexidecimal value of $i. Next, the variable $n is assigned to the equation representing the rotation of the bit at the position specified by $i to the one's position of the operand (2^0). Lastly, the %var hash is assigned the equation representing our alternate modulo 2 function applied to the rotation in $n. When all is said and done, in Perl terms, $var{'a12'} will be assigned to the equation required to rotate the bit found at the 18th position (because 12 in hexidecimal is 18 in decimal) to the one's position (also known as the least significant bit) and to evaluate it as being zero (0) or one (1).

Keeping these equations straight and typo-free is half the battle! Using the computer to do it for us greatly simplifies the remaining programming ahead.

Armed with equations to evaluate each bit of both operands (a, b), we are now in the position to program our computer to give us our bitwise XOR function. We accomplish this using the following code:

$formula= "";

for ($i=0; $i<32; $i++)
{
    $hash=sprintf("%02x", $i);
    $ai= "a".$hash;
    $bi= "b".$hash;

$formula.="((1+((-1)**($var{$ai}+$var{$bi})+"

$formula.="(-1)**(2-($var{$ai}+$var{$bi})))/(-2))/2)*2**$i+\n";
}

chop ($formula); # get rid of last newline
chop ($formula); # get rid of last (+) sign

$formula.=";"; # append semi-colon (:)

print "$formula\n"

The final formula ends up being the addition of subsequent applications of our derived XOR function using $var{$ai} and $var{$bi} (as we defined them in the previous code segment) as inputs. Using the variable $formula, we accumulate these repeated applications of our arithmetic XOR function by multiplying the output of each XOR operation by the power of 2 representing the output bit's position within the result.

When this program is executed, Perl's string substitution will faithfully reproduce the precedence and syntax of the simpler functions we needed to combine to create the complete equation. We'll then use the output from this program as paste it into another separate program for evaluation:

((1+((-1)**(((1-(-1)**($a*2**(32-0)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-0)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-0)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-0)%(2**32-1)))/2))))/(-2))/2)*2**0+
((1+((-1)**(((1-(-1)**($a*2**(32-1)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-1)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-1)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-1)%(2**32-1)))/2))))/(-2))/2)*2**1+
((1+((-1)**(((1-(-1)**($a*2**(32-2)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-2)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-2)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-2)%(2**32-1)))/2))))/(-2))/2)*2**2+
((1+((-1)**(((1-(-1)**($a*2**(32-3)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-3)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-3)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-3)%(2**32-1)))/2))))/(-2))/2)*2**3+
((1+((-1)**(((1-(-1)**($a*2**(32-4)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-4)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-4)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-4)%(2**32-1)))/2))))/(-2))/2)*2**4+
((1+((-1)**(((1-(-1)**($a*2**(32-5)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-5)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-5)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-5)%(2**32-1)))/2))))/(-2))/2)*2**5+
((1+((-1)**(((1-(-1)**($a*2**(32-6)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-6)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-6)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-6)%(2**32-1)))/2))))/(-2))/2)*2**6+
((1+((-1)**(((1-(-1)**($a*2**(32-7)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-7)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-7)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-7)%(2**32-1)))/2))))/(-2))/2)*2**7+
((1+((-1)**(((1-(-1)**($a*2**(32-8)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-8)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-8)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-8)%(2**32-1)))/2))))/(-2))/2)*2**8+
((1+((-1)**(((1-(-1)**($a*2**(32-9)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-9)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-9)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-9)%(2**32-1)))/2))))/(-2))/2)*2**9+
((1+((-1)**(((1-(-1)**($a*2**(32-10)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-10)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-10)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-10)%(2**32-1)))/2))))/(-2))/2)*2**10+
((1+((-1)**(((1-(-1)**($a*2**(32-11)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-11)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-11)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-11)%(2**32-1)))/2))))/(-2))/2)*2**11+
((1+((-1)**(((1-(-1)**($a*2**(32-12)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-12)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-12)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-12)%(2**32-1)))/2))))/(-2))/2)*2**12+
((1+((-1)**(((1-(-1)**($a*2**(32-13)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-13)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-13)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-13)%(2**32-1)))/2))))/(-2))/2)*2**13+
((1+((-1)**(((1-(-1)**($a*2**(32-14)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-14)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-14)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-14)%(2**32-1)))/2))))/(-2))/2)*2**14+
((1+((-1)**(((1-(-1)**($a*2**(32-15)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-15)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-15)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-15)%(2**32-1)))/2))))/(-2))/2)*2**15+
((1+((-1)**(((1-(-1)**($a*2**(32-16)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-16)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-16)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-16)%(2**32-1)))/2))))/(-2))/2)*2**16+
((1+((-1)**(((1-(-1)**($a*2**(32-17)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-17)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-17)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-17)%(2**32-1)))/2))))/(-2))/2)*2**17+
((1+((-1)**(((1-(-1)**($a*2**(32-18)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-18)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-18)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-18)%(2**32-1)))/2))))/(-2))/2)*2**18+
((1+((-1)**(((1-(-1)**($a*2**(32-19)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-19)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-19)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-19)%(2**32-1)))/2))))/(-2))/2)*2**19+
((1+((-1)**(((1-(-1)**($a*2**(32-20)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-20)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-20)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-20)%(2**32-1)))/2))))/(-2))/2)*2**20+
((1+((-1)**(((1-(-1)**($a*2**(32-21)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-21)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-21)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-21)%(2**32-1)))/2))))/(-2))/2)*2**21+
((1+((-1)**(((1-(-1)**($a*2**(32-22)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-22)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-22)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-22)%(2**32-1)))/2))))/(-2))/2)*2**22+
((1+((-1)**(((1-(-1)**($a*2**(32-23)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-23)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-23)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-23)%(2**32-1)))/2))))/(-2))/2)*2**23+
((1+((-1)**(((1-(-1)**($a*2**(32-24)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-24)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-24)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-24)%(2**32-1)))/2))))/(-2))/2)*2**24+
((1+((-1)**(((1-(-1)**($a*2**(32-25)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-25)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-25)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-25)%(2**32-1)))/2))))/(-2))/2)*2**25+
((1+((-1)**(((1-(-1)**($a*2**(32-26)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-26)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-26)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-26)%(2**32-1)))/2))))/(-2))/2)*2**26+
((1+((-1)**(((1-(-1)**($a*2**(32-27)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-27)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-27)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-27)%(2**32-1)))/2))))/(-2))/2)*2**27+
((1+((-1)**(((1-(-1)**($a*2**(32-28)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-28)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-28)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-28)%(2**32-1)))/2))))/(-2))/2)*2**28+
((1+((-1)**(((1-(-1)**($a*2**(32-29)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-29)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-29)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-29)%(2**32-1)))/2))))/(-2))/2)*2**29+
((1+((-1)**(((1-(-1)**($a*2**(32-30)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-30)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-30)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-30)%(2**32-1)))/2))))/(-2))/2)*2**30+
((1+((-1)**(((1-(-1)**($a*2**(32-31)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-31)%(2**32-1)))/2))+(-1)**(2-(((1-(-1)**($a*2**(32-31)%(2**32-1)))/2)+((1-(-1)**($b*2**(32-31)%(2**32-1)))/2))))/(-2))/2)*2**31;

Now that we have our equation (in a syntactically correct, Perl compatible format), we need only add a few additional Perl statements to create our finished program:

#!/usr/bin/perl

my $buf= <STDIN>;

my ($a, $b) = split /\s+/, $buf;

my $result=

print "$result\n";

We're DONE! This program was submitted as a solution to the original challenge. At this time of this writing I have not been contacted by the original poster concerning the bounty, but I am confident that we have a working program. Bounty or not, it was an interesting challenge (although I would prefer to collect the bounty :-) ) and a nice creative problem solving exercise. I'll post updates here when I get them.

We now resume our ASIC Erupter Blade discussion already in progress, thanks for reading...

DP
donation btc: 1HSFkXyLqPv1iHTjcRRw9DgiFb7SftiCxA

UPDATE: I won! Thanks Evil-Knievel!!!

Wednesday, January 29, 2014

The Bounty (Part 2)

In our last article, we discussed how to re-implement the XOR function using standard arithmetic operations and the properties of negative one (-1). Because negative one (-1) when used as a base and combined with an exponent yields only two values, it was perfectly suited to be adapted for use with a logical function.

Now, we need to step through the individual bits of each of our 32 bit operands in order to feed our XOR function. Normally we would accomplish this via a RIGHT SHIFT operation implemented either as a logical function ">>" or as division by a power of 2. In this way we could then move bits of interest to the right most (2**0) position where determinations of their value could be made by testing whether the resulting operand was even (0) or odd (1). The TRAP that must be avoided is that without access to integer math, division becomes unavailable as a means to implement our RIGHT SHIFT operation. This is because in floating point math, our discarded bits can never be discarded. As a part of floating point numbers, whenever we divide our operand to shift its bits to the right, they continue to persist as decimal fractions. We must find another way.

Programmers are creatures of habit just like everyone else. While they might be far more likely to attempt right shifting their way through each of the individual bits of our operands, rotate operations are just as valid and easy to program. The less obvious difference simply that your bits of interest have to be rotated to the ones (2**0) position from the left vs shifted (or rotated) toward the right.

For instance, if you think about a rotate operation across a 4 bit word, take the number 5 (0101) in binary for example... To rotate across a 4 bit word you have to make use of the number 2**4-1, or 15. Most programmers seeking to test the second bit position (2**1) would prefer to shift right 1 bit by doing an integer divide by 2, yielding 5/2 or 2 (0010). This moves the 2nd bit to the 2**0 position where it could be tested for eveness or oddness.

The counter-intuitive part is that we can also get the second bit into the last position where we need it using a left rotate. To accomplish this, we first multiply our operand by 8 (2**3), to shift everything 3 bits to the left:

5*8= 0101 << 3 = 0101000 (40)
(Because we are shifting left, we must shift 4-1 or 3 bits to the left...)

Next recognize that for a 4 bit word, 2**4= 1 (mod 2**4-1). This means that for every multiple of 2**4 we encounter (basically everything left of the 4th bit position), we are adding 1 (mod 2^4-1) or in other terms, that multiple multiplied by 1 (mod 2**4-1). Thus the number left of the word size accounts for the value of the bits left of 2^4 (mod 2**4-1), while all the bits right of 2**4 are either less than 2**4-1 OR 2**4-1 itself. (If all the bits right of 2**4 are 1, you can think of that as the same as 0 (mod 2**4-1))

To get the complete modulus (mod 2**4-1), we must first add the multiple of 2**4 (the number to the left of our 4 bit word) to everything mod 2**4 (the number to the right of our 4 bit word or rather our operand & 2**4-1). In other words:

(40 >> 4) + (40 & 15) = 2+8 = 10 = 1010.

If we check that against the actual 40%(2**4-1) or 40%15 we also get 10. We have rotated the bit we were interested in to the 2**0 position from the left just as we would have preferred to right shift our way there. The difference is that opposed to our disposable bit being eaten by integer division, it has appeared at the left of our 4 bit word.

Please note that although the actual value of the word has changed, it doesn't matter from the standpoint of evaluating the now least most significant bit of the operand as being even (0) or odd (1). For this challenge, this means that we can now step through each bit of both operands to evaluate the xor function in a bitwise fashion.

This part of the problem was potentially the biggest stumbling block because it required programmers to approach its solution from an unconventional direction (left rotates) vs. the approach programmers are most likely acquainted with (right shifts). Shift left (<< | *2) and shift right (>> | /2) two of the most commonly used tools in the programmer tool box, but sometimes when all you think you have is a hammer, everything else tends to resemble a nail.

Whether he knew it or not, the original poster gave us the actual tool that we needed; force of habit was probably the reason that many of us (myself included) didn't recognize it as such at first. In part 3 of this article we will put all of this information together into the program that was finally submitted for the challenge.

Stay tuned.

DP
donation btc: 1HSFkXyLqPv1iHTjcRRw9DgiFb7SftiCxA

Tuesday, January 28, 2014

The Bounty...

This past weekend while reading through the bitcointalk forums, I came across an interesting programming challenge. It read:

Hello Guys,

What you get:
Bounty of 200$ (either in BTC or wire transfer)

What you need to solve:
Simple (or less simple) algrebraic-only expression of the bitwise XOR operator. Allowed operators: powers, *, /, + and -. Also modulo (2^32-1) is allowed.
During calculation, the numerical limits of 32bit may be exceeded.
Your formula should be applicable to two unsigned integers of 32 bits.

Let the game begin

Evil-Knievel

XOR, known formally as "eXclusive OR", has always been one of several useful coding tools that programmers over the years could (for the most part) rely upon. Typically available as a logical operator in most modern programming languages, long gone have been the days of needing to actually understand the mathematical foundations of the computer logic that powers it. For most of us, it's usually been sufficient to know "what" our logical functions do versus the "how" they work.

One need not know how a car works to drive it proficiently...

There's certainly nothing wrong with that. Whether driving your car to work or employing a common logical operator in your own computer programs, one could easily make the case that there are better ways for programmers to spend their time than to figure out the mathematical foundations of the "truth tables" they all learn when first starting to code. Busy, competitive, and results driven, our world often encourages us to reach our destinations without regard to the "hows" involved.

However, for those who enjoy cars on a level beyond driving them and for those that allow themselves to be as impressed by a tool as by its function, there is both a challenge and a pleasure associated with investigating the "hows" of the tools we take for granted. There is the opportunity to learn, to accomplish, to challenge oneself and to come to appreciate the problem solving abilities of those who came before us. Most importantly, (at least in terms of this particular challenge) there is also the opportunity to make $200!

(Hey, nothing about digital coin mining is cheap and every bit helps!)

In this article we will temporarily interrupt our regularly scheduled blog to discuss the solution I found for this particular programming challenge. If there is one thing that I've missed from my college years, it's been the analysis and discussion of computer programs and computer programming as a science. This challenge involved as much math and science as one could ever want to tease their brain with. In the end, it was a problem that proved to be pleasurable in its resolution. As of this writing, I haven't gotten paid (will update here if it happens) but for those who are interested, I have the details below:

The Problem:

To implement a 32 bit XOR function using only the arithmetic operators +,-,/,*,^ and a single modulo operation: mod 2^31-1.

The XOR function:

Simply stated, the XOR function is a logical operation that accepts 2 binary digits (1 or 0) as input and outputs a single result according to the following truth table:

X Y   xor(X,Y)
0 0       0
1 0       1
0 1       1
1 1       0

One way to think of this table is in the manner that programmers learn to "sound it it out" namely the phrase "X OR Y but not BOTH". This means that where either input is a 1, and the other input is a 0, the result of the function will be 1, however where the inputs equal each other (X=Y: 1=1 or 0=0) the result of the function will be 0.

In most computer programming languages, we can express this with a simple statement:

X^Y

For a programmer, one doesn't get to be much more spoiled that that! Using the "^" (exclusive OR) operator, most compilers and interpreters will do a bitwise XOR operation using the variables X and Y. However to contemplate the distasteful, what if the "^" operator isn't available in the language that you've chosen to program your machine with? What is a poor programmer to do?

Well before you get that look that people familiar only with driving automatic transmission equipped cars get just before they get thrown behind the wheel of a manual 5 speed vehicle, I'll tell you exactly what we do:

We go back to the BASICS. We dust off our high school level arithmetic, and boldly march into battle!

If you contemplate high school level arithmetic, by the time most of us graduated, we knew about addition, subtraction, multiplication, division, exponentiation, and remainders. We learned about numbers with special properties such as 1, 0, and -1. We learned special identities for each of the mathematical operations. We learned about undefined numbers and the special circumstances where we might expect to encounter them. We learned about alternative numbering systems and we learned about how to combine all of these elements into functions such as...

xor(a,b)= (((-1)*((-1)**(a+b)+(-1)**(2-(a+b))) +2)/4

Remember that for logical functions, we make use of the binary number system where the only available digits are zero (0) and one (1). As a result, we can assume that the only values that the variables a or b will ever contain will be either 0 or 1. Enumerating all the possible combinations of a and b we can see that the sum of a+b constitutes a simple OR function:

a b a+b | (or)
0 0 0    0
1 0 1    1
0 1 1    1
1 1 2    1

In other words, the sum of a+b is non zero in all cases except where a=0 and b=0. We may also notice that the column "a+b" resembles half of the XOR truth table in that when a=0, and b=0, our result becomes 0 (just like our XOR table). What about the other half of our XOR table where a=1 and b=1 returns an output of 0? That's a little bit trickier but easily reversed by subtracting the sum of a+b from the number 2. This will give us a new column in our table where the 0 output we need for our XOR function will appear at the bottom:

a b a+b 2-(a+b)
0 0 0 2
1 0 1 1
0 1 1 1
1 1 2 0

This new table is much closer to our target XOR function, but we still need to transform it into a binary compatible output.. By "binary compatible output", our function needs to generate only two values... one or zero. To accomplish this, we turn to the number (-1). Looking closely at our revised table, we see not only zeroes in the positions where we need them, but we also see even and the odd numbers in the positions where we might need them. This is where we can employ the number negative one (-1). Negative one (-1) is special in that when used as a base, all exponents applied to it yield one of two values depending upon whether the exponent is even or odd. In the event that the exponent is even, (-1) raised to an even power yields one (1). Where the exponent is an odd, (-1) raised to an odd power yields negative one (-1). Applying this understanding, we can revise our table again:

a b (-1)**(a+b) (-1)**(2-(a+b)) sum((-1)**(a+b)+(-1)**(2-(a+b)))
0 0 1 1 2
1 0 -1 -1 -2
0 1 -1 -1 -2
1 1 1 1 2

Adding the last column which represents the sum of of (-1) raised to the power (a+b) and (-1) raised to the power (2-(a+b)) gives us a function where positive (+2) represents the cases where either a <> b, and (-2) represents the cases where a=b. At this point, we are very close to our desired output. Multiplying by the last column (-1) and adding 2 we can transform this table again:

a b (-1)**(a+b) (-1)**(2-(a+b)) (-1)*sum((-1)**(a+b)+(-1)**(2-(a+b))+2
0 0 1 1 (-1)*(+2)=(-2)+2= 0
1 0 -1 -1 (-1)*(-2)=(+2)+2= 4
0 1 -1 -1 (-1)*(-2)=(+2)+2= 4
1 1 1 1 (-1)*(+2)=(+2)+2= 0

We are now much closer to our desired result. The only thing left to do to transform this latest output into a binary compatible format (one or zero) is to divide the last column by 4.

a b (-1)**(a+b) (-1)**(2-(a+b)) (-1)*sum((-1)**(a+b)+(-1)**(2-(a+b))+2 col+2)/4
0 0 1 1 0/4= 0
1 0 -1 -1 4/4= 1
0 1 -1 -1 4/4= 1
1 1 1 1 0/4= 0

In terms of implementing the XOR function, we're done! We aren't finished with the entire challenge as given, but we now have the equation that we need to implement the full solution.

The Bitwise XOR:

Up until now we have discussed the basic XOR function in which we created a logical function equivalent that could take two binary inputs and output the value we would expect to see from the XOR truth table that we provided at the beginning of the article. We have used addition, multiplication, exponentiation and the properties of (-1) to approximate and manipulate digital values.

In fact, if we were only interested in single bit numbers, we'd be finished.

Our problem however specified that our XOR function would need to work with unsigned 32 bit numbers. Expressed in binary, these are the numbers 2**0 - 2**32-1. So given that our XOR function only works with single binary digit numbers, how can we go about XOR'ing much larger 32 bit numbers?

We convert our 32 bit inputs to their binary form and XOR their component digits in pairs. This is most commonly referred to as a bitwise XOR. To state it in simpler terms, the bitwise XOR is nothing more than the binary digits of the input numbers XOR'ed in pairs.

A : 00000001111011101111000011110000
B : 11111111000011100000110000011110
XOR: 11111110111000001111110011101110

In the second part of this article, we'll visit how a programmer typically steps through the individual bits of inputs A and B, then I'll describe how I did it so as to fit within the constraints of the original challenge.

Stay tuned...

DP
donation btc: 1HSFkXyLqPv1iHTjcRRw9DgiFb7SftiCxA

Friday, January 24, 2014

When All Else Fails, Follow the Directions...

When I was a young teenager in high school, my computer science teacher Mr. Wright had a sign in his classroom which he prominently displayed within the plain view of his students. It read: "When all else fails, follow the directions." At the time, those instructions were probably wasted on the classrooms full of 15 year olds he taught, most of whom thought they already knew everything. In retrospect I go back and forth as to whether Mr. Wright was a quixotic optimist or a wise older sage but as it turned out, my classmates and I really didn't know everything.

Fast forward a few years (ok, more than a few years...) to a newbie bitcoin enthusiast waiting for a recently purchased ASIC Erupter Blade to arrive in the mail. Rated at 10.7 gigahashes per second, I couldn't wait to install and get it working. When the blade finally arrived, it was all there: the circuit board, the power adapter, the static bag, and... no instructions. I'd seen ASIC Eruputer Blades priced from as low as $220 to as much as $600 but never had it occurred to me that such an esoteric technology might come without directions.

Sometimes, life is irony.

Thank goodness for search engines and the internet! Two weeks, many Google searches and several resolved challenges later, the ASIC Erupter Blade was mining happily, hashing away as advertised.

The focus of this blog is therefore to document my mining adventures with the ASIC Erupter Blade alongside any other mining equipment of interest that I come across. I also hope to assist you the reader in getting up and running faster by directing you past some of the pitfalls I encountered along the way. There will be equipment reviews and analyses of my costs and rewards since starting mining. In some cases, I'll even be sharing my programming expertise and some of the code I developed to make my mining rig run more autonomously.

Stay tuned...

DP
donation btc: 1HSFkXyLqPv1iHTjcRRw9DgiFb7SftiCxA