Re: [math-fun] Carry-less squaring & multiplication
Aha! So squaring p(x) (mod 2) "spreads" the bits, sending each bit a[k]x^k -> a[k]x^2k; p(x)^2=p(x^2). So we can represent perfect shuffle/interleave: p(x) shuffle q(x) = p(x)^2*x + q(x)^2 (mod 2) = p(x^2)*x + q(x^2) (mod 2) Cool! But I'd still like to know if there is a way to emulate p(x)*q(x) using cubing or fifthing, etc. At 10:13 AM 6/7/2012, Eugene Salamin wrote:
Over any field of characteristic 2, (a + b)^2 = a^2 + b^2.
If p(x) = sum(a[k] x^k, k=0..n), then p(x)^2 = sum(a[k]^2 x^(2k), k=0..n). Over the field GF(2), this further simplifies since a[k]^2 = a[k].
-- Gene
________________________________ From: Henry Baker <hbaker1@pipeline.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Thursday, June 7, 2012 9:53 AM Subject: [math-fun] Carry-less squaring & multiplication
After hearing about the new "carry-less multiplication" instructions coming soon to computers near you, it occurred to me that even without hardware help, such operations perhaps aren't so slow as I initially thought.
Karatsuba squaring.
p(x) is a polynomial over GF(2), where a "1" bit at bit position k represents 1*x^k.
Adding is easy: p(x)+q(x) (mod 2) = p(x) xor q(x). Mod 2, subtraction is the same as addition. 2*p(x) (mod 2) = 0.
If we split p(x) = q(x)*x^m+r(x) into two pieces q(x),r(x) of approximately the same size, q(x) is the "high part", and r(x) is the "low part".
Then
p(x)^2 = (q(x)*x^m+r(x))^2 = q(x)^2*x^2m + 2*q(x)*r(x)*x^m + r(x)^2 = q(x)^2*x^2m + r(x)^2 (2*anything = 0 mod 2, so middle part drops out.)
So Karatsuba squaring is almost trivial: break the poly into 2 ~ equal-sized pieces, square each piece, and then put them together with a shift & xor.
However, the ease of squaring backfires, as we can no longer use squaring to emulate multiplication:
a*b = [(a+b)^2-(a-b)^2]/4
unfortunately in GF(2) becomes:
a*b = [(a xor b)^2 xor (a xor b)^2]/0 = 0/0 !
So we need the traditional Karatsuba multiplication method:
p(x) = q(x)*x^m+r(x) s(x) = t(x)*x^m+u(x)
p(x)*s(x) = (q(x)*x^m + r(x)) * (t(x)*x^m + u(x)) = q(x)*t(x)*x^2m + ((q(x)+r(x))*(t(x)+u(x))-q(x)*t(x)-r(x)*u(x))*x^m + r(x)*u(x) = q(x)*t(x)*x^2m xor ((q(x) xor r(x))*(t(x) xor u(x)) xor q(x)*t(x) xor r(x)*u(x))*x^m xor r(x)*u(x)
----- Question:
Is it possible to emulate multiplication using p(x)^3 or p(x)^5 (mod 2) ?
On Thursday 07 June 2012 18:31:13 Henry Baker wrote:
Aha! So squaring p(x) (mod 2) "spreads" the bits, sending each bit a[k]x^k -> a[k]x^2k; p(x)^2=p(x^2).
So we can represent perfect shuffle/interleave:
p(x) shuffle q(x) = p(x)^2*x + q(x)^2 (mod 2) = p(x^2)*x + q(x^2) (mod 2)
The designers of INTERCAL were prescient indeed. -- g
="Henry Baker" <hbaker1@pipeline.com> Aha! So squaring p(x) (mod 2) "spreads" the bits, sending each bit a[k]x^k -> a[k]x^2k; p(x)^2=p(x^2).
A000695[k], the Moser-de Bruijn sequence, with many interesting properties. For example you can map a pair of integers x,y to a single integer z via z = a[x] + 2 a[y] then you can interleave another integer w via a[w] + 2 a[z] and so on... If you're interested in more on carryless arithmetics, including in bases other than binary, digit-sum rules other than modulo the base and more, you might like http://arxiv.org/abs/1008.4633 and http://arxiv.org/abs/1107.1130
Thanks for the reference. A000695 doesn't (directly) reference squared polynomials over GF(2), but I'm sure that some/many of the A000695 references do. A significant use of "perfect shuffle"/"interleave" is so-called "Z-order" or "Morton order" code which maps 2-dimensional integral coordinates into 1-dimensional coordinates by interleaving the bits of the x and y coordinates. The inverse of this function produces a space-filling "curve". http://en.wikipedia.org/wiki/Z-order_curve I wonder if anything interesting happens by mapping the coordinates of Gaussian integers into normal integers by interleaving the bits of the real and imaginary coordinates. At 10:15 PM 6/7/2012, Marc LeBrun wrote:
="Henry Baker" <hbaker1@pipeline.com> Aha! So squaring p(x) (mod 2) "spreads" the bits, sending each bit a[k]x^k -> a[k]x^2k; p(x)^2=p(x^2).
A000695[k], the Moser-de Bruijn sequence, with many interesting properties.
For example you can map a pair of integers x,y to a single integer z via z = a[x] + 2 a[y] then you can interleave another integer w via a[w] + 2 a[z] and so on...
If carryless addition over GF2 is XOR, that implies the truth table: +|0 1 -+--- 0|0 1 1|1 0 Therfore, given multiplication would look like: *|0 1 -+--- 0|0 0 1|0 1 then multiplicate is AND, yes? What am I missing? -JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6
Yes, that's correct. Now consider polynomials p(x) with 0,1 coefficients and XOR,AND for +,*. One can also consider p(x) mod q(x), but we aren't doing that here (yet). At 08:40 AM 6/8/2012, James Cloos wrote:
If carryless addition over GF2 is XOR, that implies the truth table:
+|0 1 -+--- 0|0 1 1|1 0
Therfore, given multiplication would look like:
*|0 1 -+--- 0|0 0 1|0 1
then multiplicate is AND, yes?
What am I missing?
-JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6
* James Cloos <cloos@jhcloos.com> [Jun 08. 2012 19:06]:
If carryless addition over GF2 is XOR, that implies the truth table:
+|0 1 -+--- 0|0 1 1|1 0
Therfore, given multiplication would look like:
*|0 1 -+--- 0|0 0 1|0 1
then multiplicate is AND, yes?
correct
What am I missing?
nothing (btw. OR is saturating addition).
-JimC -- James Cloos <cloos@jhcloos.com> OpenPGP: 1024D/ED7DAEA6
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Fri, Jun 8, 2012 at 8:40 AM, James Cloos <cloos@jhcloos.com> wrote:
If carryless addition over GF2 is XOR, that implies the truth table:
+|0 1 -+--- 0|0 1 1|1 0
Therfore, given multiplication would look like:
*|0 1 -+--- 0|0 0 1|0 1
then multiplicate is AND, yes?
What am I missing?
Nothing for GF(2). The ring of polynomials GF(2)[x] has elements like p(x) = x^3 + x + 1 which is the same as p(x) = x^3 - x - 1. To multiply polynomials in GF(2)[x], you do it the normal way, but then you reduce the coefficients mod 2. To get the number field GF(2^n), we mod out GF(2)[x] by an irreducible polynomial p(x) of degree n. The p(x) above is irreducible, so we can form GF(2^3) as GF(2)[x]/(x^3-x-1). The elements are 0 1 x x^2 x^3 = x + 1 x^4 = x^2 + x x^5 = x^2 + x + 1 x^6 = x^2 + 1 and we have x^7 = 1. We can represent each of these elements in binary as the vector of its coefficients. When we do that, multiplying by x is the same as clocking a linear feedback shift register. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
participants (6)
-
Gareth McCaughan -
Henry Baker -
James Cloos -
Joerg Arndt -
Marc LeBrun -
Mike Stay