4
\$\begingroup\$

Interpret a triple of 32-bit integers as a vector of 32 integers modulo 5. Write an addition routine for these vectors.

Example:

def add32((a0,a1,a2),(b0,b1,b2)):
    c0 = c1 = c2 = 0
    m = 1
    for i in range(32):
        a  = ((a0//m)&1) + 2*((a1//m)&1) + 4*((a2//m)&1)
        b  = ((b0//m)&1) + 2*((b1//m)&1) + 4*((b2//m)&1)
        c  = (a+b)%5
        c0+= m*(c&1)
        c1+= m*((c&2)//2)
        c2+= m*((c&4)//4)
        m += m
    return c0,c1,c2

Note:

You only need to be internally consistent, not consistent with my sample code. If you use a different representation of the integers mod 5, that's fine as long as you provide a translation table of the form:

0 = 000 or 101
1 = 001 or 110
2 = 010 or 111
3 = 011
4 = 100

Scoring:

Characters + number of arithmetic operations required. The sample code takes 331 characters and 34 operations per bit (note that I'm not counting the function call or iteration, nor interpreter overhead); hence gets a score of 331+1056=1686.

Clarification:

This is a trick called bitslicing. It's natural to pack integers mod 5 directly into words (spaces added for clarity:

0 1 2 3 4 -> 000 001 010 001 101

but you end up sacrificing a few bits at the end of each word. To keep your data aligned but pack the most in, store the data in slices

                 0 0 0 0 1 = a2
a = 0 1 2 3 4 -> 0 0 1 1 0 = a1
                 0 1 0 1 0 = a0

Example 2

A language-agnostic example was requested, so here it is. Suppose we use the representation

0 = 100
1 = 001
2 = 010 or 101
3 = 110
4 = 011

and 111 and 000 are meaningless. Then, the following sum is valid according to our representation:

                  1 0 0 1 1 0 1 0
0 1 2 2 3 4 0 2 = 0 0 1 0 1 1 0 1
                  0 1 0 1 0 1 0 0
+
                  0 1 0 0 1 0 1 1
1 2 1 2 0 1 0 3 = 0 0 0 1 0 0 0 1
                  1 1 1 0 0 1 0 0
---------------------------------
                  0 1 1 0 1 1 1 1 
1 3 3 4 3 0 0 0 = 0 1 1 1 1 0 0 0
                  1 0 0 1 0 0 0 0

Remark

As Keith Randall has demonstrated, this can be done with all bits in parallel using logical operators. We can view such a solution as a circuit with a certain number of gates. Perhaps I should call this "circuit golf". I chose 5 instead of 3 because it's too easy to brute-force (optimal is 6 gates/trit).

\$\endgroup\$
5
  • 5
    \$\begingroup\$ BORING!!! No more plain math, please. \$\endgroup\$ – Oleh Prypin Jul 4 '11 at 7:43
  • 1
    \$\begingroup\$ Can you give some small samples, maybe using bytes instead of 32-bit ints. \$\endgroup\$ – user unknown Jul 4 '11 at 8:56
  • \$\begingroup\$ I count 34 ops inside the loop, not 32. By lines: 10 + 10 + 2 + 3 + 4 + 4 + 1 = 34. \$\endgroup\$ – Matthew Read Jul 4 '11 at 17:51
  • \$\begingroup\$ Can you please give a language-agnostic description of what the code is supposed to do, and some sample input/output, or do you only want answers in Python ? \$\endgroup\$ – Paul R Jul 4 '11 at 21:42
  • \$\begingroup\$ It is difficult to count the number of "ops" in different languages. If you take eg. Brainfuck, you need a lot of ops while in another language it might be only a few. That said, some languages provide more powerful ops than others, so the rating is a bit biased. \$\endgroup\$ – FUZxxl Jul 4 '11 at 21:50
5
\$\begingroup\$

Python, score=215 166 (167 118 chars, at most 48 ops)

def A(x,y,z,p,q,r):
 u,c=x^p,x&p;v,d=y^q^c,y&q|y&c|q&c;w,e=z^r^d,z&r|z&d|r&d
 if e:u,v,w=A(e,e,0,u,v,w)
 return u,v,w

Does addition in bit-parallel. The c,d,e are the 32 carries from one position to the next. e represents multiples of 8 that carry out of the vector, so if e has any bits set in it, we add 8%5=3 back in using a recursive call.

The translation table is the same as the one given in the question.

\$\endgroup\$
1
  • 4
    \$\begingroup\$ You can save 43 chars by using single-digit names. And another 3 by concatenating assignments to d0,c0 and d1,c1 and d2,c2 by commas. \$\endgroup\$ – Howard Jul 4 '11 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.