June 2012 - mathfun@mailman.xmission.com

[math-fun] Gibbs phenomenon, agree infinite arc-length
by Warren Smith 08 Jun '12

08 Jun '12

Wikipedia http://en.wikipedia.org/wiki/Gibbs_phenomenon probably does not have a very good discussion. But anyhow, they claim the heights of the Gibbs phenomenon peaks asymptotically are given by (for the Nth peak; note N=even yields "reverse peaks" below 1, N=odd yields "normal peaks" above 1) integral from -infinity to N sin(pi*x)/(pi*x) dx If so, then I agree: the height differences between successive peaks clearly behave eventually proportionally to 1/N for the Nth peak. Hence the Fourier reconstruction of the unit step function will in the limit (where we get pointwise convergence to that step function at any fixed x>0 or any fixed x<0, hence the Gibbs peaks all horizontally move closer together) indeed will have arc-length tending to infinity over any fixed finite segment of the x-axis containing 0 inside it. -- Warren D. Smith http://RangeVoting.org

1 0

Re: [math-fun] carryless multiplication (or other techniques?) for bit-permuting
by Henry Baker 08 Jun '12

08 Jun '12

I've investigated Warren's permutation problem in several different guises. I studied how to implement arbitrary permutations in APL using the APL transpose & restructure operations. If we have an n-dimensional array in APL, transpose can exchange indices; if we have a vector in APL, restructure can give it a new interpretation as an n-dimensional array. I also studied how to implement arbitrary permutations on the top k elements of a stack (in a stack machine). And then there's also Warren's bit-permutation problem. The basic problem in all of these permutation problems is straight-forward information theory: how many bits does it take to specify which permutation you're talking about in the first place. If all permutations are equally likely than we have log(n!) ~ O(n*log(n)) bits. So even if you wanted to specify an arbitrary permutation of the 64 bits in a 64-bit word, you would need 296 bits (= log2(64!)). At 10:33 AM 6/8/2012, Warren Smith wrote: >It is not so easy to permute bits, actually. > >Say you have a W-bit word (W=64?). >You want to permute the lower-significance K bits in >some arbitrary known manner. How do you do it? >Here is one way: > >Step 1: multiply by 100001000010000... where the period is K. >Carryless or regular multiply both work here and below. > >Step 2: AND with some magic bit mask with one 1-bit per K-chunk >chosen to get exactly one copy of each original bit, one per chunk, >ordered in arbitrary known order. > >Step 3: multiply by the correct magic sparse-1's number so that >the correct permuted K bits magically appear in the most-signif K bits >of the product word. It is possible here that if you are using >regular (not carryless) multiply, you will need about log(K) buffer bits >between the top K bits used for output, and the bottom K*K bits >used for input. > >Step 4: shift right by W-K+BuffSize hops to reposition in original K >bit locations. > >This works if BuffSize+K*K<=W, so if W=64 we can permute 8 bits >with carryless, and maybe somewhat fewer with regular, multiply. > >That sucks. I mean, to permute 8 bits I could've just used >a 256-byte lookup table. > >Looking in the FxtBook, http://www.jjj.de/fxt/fxtbook.pdf >section 1.29 fails to answer the question though it does suggest >future machine instructions that would.

2 1

Re: [math-fun] carryless multiplication (or other techniques?) for bit-permuting
by Henry Baker 08 Jun '12

08 Jun '12

Very cool! Thanks! At 12:35 PM 6/8/2012, Bill Gosper wrote: >In case anyone missed it, Knuth is strongly pushing MMIX's MOR and MXOR for commercial 64 bit processors. > >www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz

1 0

[math-fun] carryless multiplication (or other techniques?) for bit-permuting
by Bill Gosper 08 Jun '12

08 Jun '12

In case anyone missed it, Knuth is strongly pushing MMIX's MOR and MXOR for commercial 64 bit processors. www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz --rwg All hail the БЕСМ 6. WDS: It is not so easy to permute bits, actually. Say you have a W-bit word (W=64?). You want to permute the lower-significance K bits in some arbitrary known manner. How do you do it? Here is one way: Step 1: multiply by 100001000010000... where the period is K. Carryless or regular multiply both work here and below. Step 2: AND with some magic bit mask with one 1-bit per K-chunk chosen to get exactly one copy of each original bit, one per chunk, ordered in arbitrary known order. Step 3: multiply by the correct magic sparse-1's number so that the correct permuted K bits magically appear in the most-signif K bits of the product word. It is possible here that if you are using regular (not carryless) multiply, you will need about log(K) buffer bits between the top K bits used for output, and the bottom K*K bits used for input. Step 4: shift right by W-K+BuffSize hops to reposition in original K bit locations. This works if BuffSize+K*K<=W, so if W=64 we can permute 8 bits with carryless, and maybe somewhat fewer with regular, multiply. That sucks. I mean, to permute 8 bits I could've just used a 256-byte lookup table. Looking in the FxtBook, http://www.jjj.de/fxt/fxtbook.pdf section 1.29 fails to answer the question though it does suggest future machine instructions that would. ---- There, there, JJ, that's an English-speaker's mistake!

1 0

Re: [math-fun] Carry-less squaring & multiplication
by Henry Baker 08 Jun '12

08 Jun '12

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(a)pipeline.com> >>To: math-fun <math-fun(a)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) ?

6 7

[math-fun] carryless multiplication (or other techniques?) for bit-permuting
by Warren Smith 08 Jun '12

08 Jun '12

It is not so easy to permute bits, actually. Say you have a W-bit word (W=64?). You want to permute the lower-significance K bits in some arbitrary known manner. How do you do it? Here is one way: Step 1: multiply by 100001000010000... where the period is K. Carryless or regular multiply both work here and below. Step 2: AND with some magic bit mask with one 1-bit per K-chunk chosen to get exactly one copy of each original bit, one per chunk, ordered in arbitrary known order. Step 3: multiply by the correct magic sparse-1's number so that the correct permuted K bits magically appear in the most-signif K bits of the product word. It is possible here that if you are using regular (not carryless) multiply, you will need about log(K) buffer bits between the top K bits used for output, and the bottom K*K bits used for input. Step 4: shift right by W-K+BuffSize hops to reposition in original K bit locations. This works if BuffSize+K*K<=W, so if W=64 we can permute 8 bits with carryless, and maybe somewhat fewer with regular, multiply. That sucks. I mean, to permute 8 bits I could've just used a 256-byte lookup table. Looking in the FxtBook, http://www.jjj.de/fxt/fxtbook.pdf section 1.29 fails to answer the question though it does suggest future machine instructions that would.

1 0

Re: [math-fun] Gun problem
by Dan Asimov 08 Jun '12

08 Jun '12

What happens here seems very clear after drawing one time-vs.-distance plot for each bullet on the tx-plane -- assuming one bullet per second. * Each speed-2 bullet annihilates the most recent speed-1 bullet after 1 second. Unless of course the speed-2 bullet is the first one, in which case it goes forever in a straight line. --Dan Jim wrote (re David's Gun Problem): << . . . I'd also like to see what happens with a non-random gun that simply alternates between emitting speed-1 bullets and speed-2 bullets; probably it gives something with a simple fractal structure, but I'm too tired right now to do by-hand simulations or to code. . . . >> ________________________________________________________________________________________ It goes without saying that .

4 3

[math-fun] carryless multiplication
by Warren Smith 08 Jun '12

08 Jun '12

It can be used to perform an arbitrary bit-permutation within a binary word, something I recently wanted to do. However... you have to have the right hardware, and I think I don't.

1 0

Re: [math-fun] Wiki article on Circumscribed_circle
by Henry Baker 08 Jun '12

08 Jun '12

You have to ask yourself, who _are_ these "senior researchers", anyway? What sort of person sits around all day waiting for someone to make a change to an obscure page of Wikipedia, only to pounce on the offender (anonymously, of course). Since (to my knowledge), these people aren't getting paid, I can't imagine what sort of personality would find this sort of anonymous pouncing to be enjoyable or fulfilling. But then I am reminded that upwards of 33% of the East Germans willingly spied on the other 67% (probably the 33%, too!), and for apparently _no money, or any other consideration_ ! This sort of behavior _has_ to be genetic; else how else could such behavior be so widespread? I'm reminded of the librarian who looked extremely depressed & upset. When asked what the problem was, she (librarians were always "she" in those days) said "Someone took a book out today." "But I'm going to make sure that I get it back!" At 01:09 PM 6/4/2012, J J wrote: >You see, this is exactly where No Original Research falls flat on its face. > >The required competency for checking Henry's math would pass as "doing research" to most Wikipedian authorities. > >My own experience editing Wikipedia is similar to Henry's. > >After trying, unsuccessfully, to remove some clearly bogus pseudo-science (clearly bogus by several standard textbooks) from a physics article, I cited anotherWikipediaarticle that (clearly and obviously to me) disagreed with the first. > >I was told, by a "senior editor", that there was no way that they could enforce that articles be consistent with each other. > >On June 3, 2012 at 10:59 AM Henry Baker <hbaker1(a)pipeline.com> wrote: >>Ã Just check the math, and if it is correct, allow it.

2 2

[math-fun] Wiki article on Circumscribed_circle
by Henry Baker 08 Jun '12

08 Jun '12

Does anyone know how to deal with Wikipedia? I tried this morning to make a very modest edit to the Circumscribed_circle article, and someone else keeps reverting it back. All I'm trying to do is to add an external link to my article about computing the circumcenter coordinates using complex numbers: http://home.pipeline.com/~hbaker1/FAQ-circumcircle.txt My result is a generalization of the classic formula: R=abc/(4 A), where R is the radius of the circumcircle, a,b,c are the side-lengths, and A is the area. Now consider R,a,b,c to be "vectors" in the complex plane -- i.e., complex numbers. Then the previous formula is |R|=|a||b||c|/(4 A) My formula is: R = -ia'bc/(4 A) where i=sqrt(-1), and a' is conjugate(a). Note that the multiplications in my formula are now _complex_ multiplies. I think that this is a cool formula, and I believe that Gosper thought so, too. Can someone here please help me make this change? Thanks.

5 5