Three Parts of Division

I was going to update this blog at some point.

I'm back to solving problems on Project Euler. I've solved the easy ones, and now I'm getting around to the medium difficulty problems. I like #26.

Problem 26: Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

That's kinda interesting. Every time you divide two numbers, there are three parts: The integer part, the non-repeating decimal part, and the repeating decimal part.

I wrote up this little piece of Python to compute the three parts. It is a forced base-10 long division calculator, and it makes good use of Python's stings doubling as list, which is a feature that I always thought was nice about Python.

def division(num, den):
    ipart = str(num / den);
    fpart = ""
    rpart = ""
    seen  = [ num%den ]
    while num % den != 0:
        num        = (num%den) * 10
        multiple   = num / den
        fpart     += str(multiple)
        num        = num - (den * multiple)
        c = 0
        quit = False
        for i in seen:
            if num == i: # This number has been seen before.
                rpart = fpart[c:] # Make characters from c to end of list part of repeating part
                fpart = fpart[:c] # Truncate fpart
                quit = True
                break
            c = c + 1
        if quit:
            break
        seen += [num]
    return [ipart, fpart, rpart]

This method accepts two arguments: An integer numerator and an integer denominator. The return is a list with three items: The whole number part, the non-repeating decimal part, and the repeating decimal part. Each part is a string data type (because sometimes these parts can be excessively long for python's Integer type.)

>>> division(1,4)
['0', '25', '']
>>> division(1,6)
['0', '1', '6']
>>> division(1,7)
['0', '', '142857']

XOR Logic

It's winter break, so I have had less "essential" programming to do. I have been wasting time on projecteuler.net. This site is an on-line competition devoted to solving very difficult math problems of the type that require programs to solve. I've been on the site for about two weeks and I've solved a third of the problems.

The problem that has interested me the most is problem #59: Brute force decryption using XOR Logic. I can't talk about the solution here, because that would only help people who are trying to win the competition by Googling answers, but I can talk about XOR Logic.

XOR Logic is the comparison between two items where the results is true if one is true and the other isn't. If both are false or if both are true, the result is false. In programming terms, we think of it like this:

unsigned char a, b, c;
scanf("%c",&a);
scanf("%c",&b);
c = (~a&b)|(a&~b); // XOR Logic Here!
printf("%c(%d) -> %c(%d) -> %c(%d)\n", a,a, b,b, c,c);

In this example, we have two terms: a and b. We wish to XOR these two items to make a result c. Using C's bitwise and "&", bitwise or "|", and bitwise negate "~", we can create the XOR gate. We have two inputs, and one has to be true and the other must be false for the result to be true. It doesn't matter the order. Output c is true if input a is true and input b is false or if a is false and b is true. In fact, that sentence is pretty much how I programmed it.

English:
Output c is true if input a is true and input b is false
or if a is false and b is true.

English and C:
Output c is true [c = ] if [(] input a is true [a] and(&)
input b is false[~b] [)] or[|] if[(] a is false[~a] and[&]
b is true[b] [)].[;]

C:
c = (~a&b)|(a&~b);

So how is this useful? Cryptography is based on the practice of taking a message, encrypting it, then taking the encrypted message and decrypting it. The great thing about XOR logic is that it is used for both encrypting and decrypting text.

Let's say that your secret message consist of one character: "L". "L" on the ASCII table is decimal 76 or binary "01001100". You need a secret password to encrypt the letter "L". For that, we'll use "!" which is decimal 33 or binary "00100001".

01001100 L (76)
00100001 ! (33)
-------- XOR
01101101 m (109)

"L" has now been encrypted. The encrypted text is now "m". Using our password "!", we can now decrypt the text:

01101101 m (109)
00100001 ! (33)
-------- XOR
01001100 L (76)

We just decrypted our message "m" using the same XOR method and password "!" that we used to encrypt the message. XOR Logic is pretty useful because it provides the method to both encrypt and decrypt messages quickly.

Matrix Fun in Haskell

I have always thought that the snobbiest of programmers are those that use Haskell, which is a language so academic that I'm not sure if it's been used outside academia. Haskell is known for what it doesn't have. Haskell doesn't have the same loop structure. It doesn't have variables. It doesn't have the imperative design like most languages. I like Haskell. Any time I need to jump on a math program, I usually solve it in Haskell first, then the language I need second.

A friend of mine is a physics Ph.D. student who is trying to learn C. He wanted to write a program to find all of the 2-by-2 determinants found in a 4-by-4 matrix. There are 36 total. He had his own ideas on how to solve this, but I still think the quickest way is to brute force all of the possibilities.

The following patches of Haskell and C are almost identical. They use the exact same variables ("labels" for the Haskell code) to accomplish the same task. The Haskell code returns an array of floats, where the C code prints each of the 36 determinants.

twoByTwo :: [[Float]] -> [Float]
twoByTwo m = concat (map(\i->
                 concat (map(\j->
                     concat (map(\p->
                         map(\q->
                             (m!!i!!j)*(m!!p!!q)-(m!!i!!q)*(m!!p!!j)
                         )[(j+1)..(n-1)]
                     )[(i+1)..(n-1)])
                 )[0..(n-2)])
             )[0..(n-2)])
             where
                 n = length m

Yes, Haskell fans, there is a quadruple-nested lambda expression there, which does seem a little confusing. It's short and elegant, which is why Haskell reminds me of Python.

void twoByTwo(float *m, int n) {
    int i, j, p, q;
    for (i = 0; i < n-1; i++)
        for (j = 0; j < n-1; j++)
            for (p = i+1; p < n; p++)
                for (q = j+1; q < n; q++)
                    printf("%3.1f\n", m[i*n+j]*m[p*n+q] - m[i*n+q]*m[p*n+j]);
}

No one ever said C was pretty. I also wrote a recursive Matrix determinant algorithm in Haskell, but I may save that for another time.