[math-fun] 1869 MIT entrance exam; SHA1 progress; Xor multiply
Tech Review has put online the 1869 MIT entrance exam. http://libraries.mit.edu/archives/exhibits/exam/arithmetic.html There are 4 parts, English, Arithmetic, Algebra, Geometry. The math parts are relatively easy, corresponding to grade level 10.5, the middle of sophomore year in US high school. I found the English section more challenging: The language skills section is undoable -- the source text to be analyzed is missing. There are questions on history, literature, geography, and current events. I was especially surprised to do badly on the geography questions: I've been to Europe multiple times, and couldn't say exactly where Vienna is, nor describe the course of the Danube. ---- SHA1 update [some funsters have crypto interests] Some respectable cryptographers claim to have reduced the effort to find a SHA1 collision to 2^52 hash computations. Their slides are posted at http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf The presentation is too sketchy to evaluate yet, but the authors are well known. The collision work is about 20 years on a late model PC. ---- Xor Multiply Intel is introducing the PCLMULQDQ instruction, which does a 64x64->128 bit Xor-Multiplication. (Their naming conventions remind me of the Tom Lehrer song about the Red Line.) This instruction is helpful in several crypto applications, and also in working with error correcting codes. Puzzle: a) Use the new instruction in a routine to reverse 64 bits. This swaps the sign bit with the low order bit, etc. b) The new instruction can obviously be used to Xor-Square a 64-bit quantity. Use it to do "square root": collect the odd numbered bits 63-1 in the left half of the word, and the even numbered bits 62-0 in the right half. c) Extra credit: describe the relationship with card shuffling. d) Is PCLMULQDQ useful in implementing an arbitrary pre-specified bit permutation? Rich
Tech Review has put online the 1869 MIT entrance exam.
http://libraries.mit.edu/archives/exhibits/exam/arithmetic.html
There are 4 parts, English, Arithmetic, Algebra, Geometry. The math parts are relatively easy, corresponding to grade level 10.5, the middle of sophomore year in US high school. I found the English section more challenging: The language skills section is undoable -- the source text to be analyzed is missing. There are questions on history, literature, geography, and current events. I was especially surprised to do badly on the geography questions: I've been to Europe multiple times, and couldn't say exactly where Vienna is, nor describe the course of the Danube.
----
SHA1 update
[some funsters have crypto interests] Some respectable cryptographers claim to have reduced the effort to find a SHA1 collision to 2^52 hash computations. Their slides are posted at
http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf
The presentation is too sketchy to evaluate yet, but the authors are well known. The collision work is about 20 years on a late model PC.
---- Knuth is *emphatically* calling for 8x8bit matrix multiply, both xor and ior. --rwg HOLLERITH'S THILL HORSE SPERMATHECAL CHAPELMASTER COMEALONG MEGACOLON HORSE PISTOL STROPHIOLES RIND DISEASE DIARSENIDES
Xor Multiply
Intel is introducing the PCLMULQDQ instruction, which does a 64x64->128 bit Xor-Multiplication. (Their naming conventions remind me of the Tom Lehrer song about the Red Line.) This instruction is helpful in several crypto applications, and also in working with error correcting codes.
Puzzle: a) Use the new instruction in a routine to reverse 64 bits. This swaps the sign bit with the low order bit, etc. b) The new instruction can obviously be used to Xor-Square a 64-bit quantity. Use it to do "square root": collect the odd numbered bits 63-1 in the left half of the word, and the even numbered bits 62-0 in the right half. c) Extra credit: describe the relationship with card shuffling. d) Is PCLMULQDQ useful in implementing an arbitrary pre-specified bit permutation?
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
(1/prod(x-cos(2*%pi*j/n+f),j,1,n) = 2^(n-1)/(cos(n*acos(x))-cos(f*n))) = 2^(n-1)*(sum(sin(2*%pi*k/n+f)/(x-cos(2*%pi*k/n+f)),k,1,n))/(n*sin(f*n)) n - 1 1 2 --------------------------- = ---------------- n T (x) - cos(f n) /===\ n | | 2 j pi | | (x - cos(------ + f)) | | n j = 1 n 2 k pi ==== sin(------ + f) n - 1 \ n 2 > ------------------- / 2 k pi ==== x - cos(------ + f) k = 1 n = -------------------------------- n sin(f n) where T (x) := cos(n acos(x)), the nth Tchebychev polynomial. So n 1/\t[n](x) = sum(sin(%pi*(4*k+1)/(2*n))/(x-cos(%pi*(4*k+1)/(2*n))),k,1,n)/n n (4 k + 1) pi ==== sin(------------) \ 2 n > --------------------- / (4 k + 1) pi ==== x - cos(------------) 1 k = 1 2 n ----- = ---------------------------, n>0. T (x) n n Dividing the first equation into itself with x=0, then x <- 1/x, then logderiv wrt x: sum(1/(x-sec(2*%pi*j/n+f)),j,1,n) = n/x-n*chebyshev_u[n-1](1/x)/((chebyshev_t[n](1/x)-cos(f*n))*x^2) n 1 ==== n U (-) \ 1 n n - 1 x > ------------------- = - - --------------------- / 2 j pi x 1 2 ==== x - sec(------ + f) (T (-) - cos(f n)) x j = 1 n n x where d 2 -- (T (x)) sqrt(1 - T (x)) sin(n acos(x)) dx n n U (x) = -------------- = ---------- = ---------------. n - 1 2 n 2 sqrt(1 - x ) sqrt(1 - x ) -d/dx squares the summand with considerable inelegance on the rhs: sum(1/(x-sec(2*%pi*j/n+f))^2,j,1,n) = n*(('chebyshev_u[n-1](1/x)*(2*x^2-1)/x+n*sin(f*n)^2/(cos(f*n)-'chebyshev_t[n](1/x))+n*cos(f*n))/((cos(f*n)-'chebyshev_t[n](1/x))*(x^2-1))+1)/x^2 n ==== \ 1 > ---------------------- / 2 j pi 2 ==== (x - sec(------ + f)) j = 1 n 1 2 U (-) (2 x - 1) 2 n - 1 x n sin (f n) -------------------- + ---------------- + n cos(f n) x 1 cos(f n) - T (-) n x n (---------------------------------------------------- + 1) 1 2 (cos(f n) - T (-)) (x - 1) n x = ------------------------------------------------------------. 2 x --rwg PAINT HORSES SENATORSHIP SPHERATIONS
1. How much of this was part of Iverson's original (the book, not the movie^H^H^H^H^Htimeshared programming language) language "APL" ? 2. How many other "hidden" instructions does Intel and/or AMD have in their chips thanks to the Boys(&girls) from Baltimore? Has anyone fully explored the Intel/AMD order code set for any ghost instructions? --- Lisp/Haskell/whatever has "mapping" mechanisms, but many looping constructs really want "convolution" mechanisms. E.g., when processing sequences of GPS points, I don't just want to examine the points individually, but may want to compute incremental distances, speeds, & possibly apply 3rd order filters. Which languages already offer elegant convolution-type mechanisms? There used to be a version of Fortran that automatically computed derivatives (various levels of differences) which could do some of these things. It never seemed to have caught on. At 10:07 PM 5/2/2009, rwg@sdf.lonestar.org wrote:
Knuth is *emphatically* calling for 8x8bit matrix multiply, both xor and ior. --rwg
Xor Multiply
Intel is introducing the PCLMULQDQ instruction, which does a 64x64->128 bit Xor-Multiplication. (Their naming conventions remind me of the Tom Lehrer song about the Red Line.) This instruction is helpful in several crypto applications, and also in working with error correcting codes.
Puzzle: a) Use the new instruction in a routine to reverse 64 bits. This swaps the sign bit with the low order bit, etc. b) The new instruction can obviously be used to Xor-Square a 64-bit quantity. Use it to do "square root": collect the odd numbered bits 63-1 in the left half of the word, and the even numbered bits 62-0 in the right half. c) Extra credit: describe the relationship with card shuffling. d) Is PCLMULQDQ useful in implementing an arbitrary pre-specified bit permutation?
Rich
* rcs@xmission.com <rcs@xmission.com> [May 04. 2009 11:50]:
[...]
Xor Multiply
Intel is introducing the PCLMULQDQ instruction, which does a 64x64->128 bit Xor-Multiplication. (Their naming conventions remind me of the Tom Lehrer song about the Red Line.) This instruction is helpful in several crypto applications, and also in working with error correcting codes.
Puzzle: a) Use the new instruction in a routine to reverse 64 bits. This swaps the sign bit with the low order bit, etc.
Uhm, dunno. And I'd like to know. I use a method similar to the code given for (b), it needs less than 10 cycles if a byte-swap instruction is available.
b) The new instruction can obviously be used to Xor-Square a 64-bit quantity. Use it to do "square root": collect the odd numbered bits 63-1 in the left half of the word, and the even numbered bits 62-0 in the right half.
Using 8 bit words here: squaring: abcdABCD --> a0b0c0d0,A0B0C0D0 compute aAbBcCdD == a0b0c0d0 XOR ( A0B0C0D0 >> 1 ) [I call this operation bit-zip] repeat to get acACbdBD (which is what we want) I doubt this wil be much better than the well known methods, unless immediate operands are expensive (or unavailable, as in yucky SSE). Here is essentially what I use: static inline ulong bit_unzip(ulong x) // Return word with even indexed bits in lower half // and odd indexed bits in higher half. { ulong y = (x >> 1) & 0x5555555555555555UL; x &= 0x5555555555555555UL; x = (x | (x>>1)) & 0x3333333333333333UL; y = (y | (y>>1)) & 0x3333333333333333UL; x = (x | (x>>2)) & 0x0f0f0f0f0f0f0f0fUL; y = (y | (y>>2)) & 0x0f0f0f0f0f0f0f0fUL; x = (x | (x>>4)) & 0x00ff00ff00ff00ffUL; y = (y | (y>>4)) & 0x00ff00ff00ff00ffUL; x = (x | (x>>8)) & 0x0000ffff0000ffffUL; y = (y | (y>>8)) & 0x0000ffff0000ffffUL; x = (x | (x>>16)) & 0x00000000ffffffffUL; y = (y | (y>>16)) & 0x00000000ffffffffUL; x |= (y<<32); return x; }
c) Extra credit: describe the relationship with card shuffling.
one step as above (my 'bit-zip') is an outer shuffle(?)
d) Is PCLMULQDQ useful in implementing an arbitrary pre-specified bit permutation?
That would be nice 8-) A few important permutations (like zip/unzip or rev-bin, which have clean decompositions as Kronecker products) can be obtained with methods similar to the above.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Henry Baker -
Joerg Arndt -
rcs＠xmission.com -
rwg＠sdf.lonestar.org