- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] New? multiplicaiton of GF2 polynomials
by Schroeppel, Richard 30 Jun '06

30 Jun '06

Before log tables were invented, there were a couple of other tricks that were useful for multiplication. One way was to use trig identities like cosX * cosY = (cos(X+Y) + cos(X-Y))/2. Another was to use a table of triangular numbers, T(x) = x(x+1)/2 x * y = T(x+y) - T(x) - T(y) or Quarter-Squares, Q(N) = floor[N^2 / 4] x * y = Q(x+y) - Q(x-y). The key idea in each case is to use a table that's a function of one variable in a clever way to compute a two-variable result. (I'm skeptical about these actually being used much, since the required tables are still pretty big. But I've never actually looked over Mr. Fibonacci's shoulder.) I'm looking for an appropriate generalization for GF2 polynomial multiplication. (Multiplication of polynomials where the coefficients are reduced mod 2.) Each of the methods above uses division by 2, so some minor variation is necessary. There are about six different ways to do GF2 polynomial products. I'm wondering if the scheme below is new. Define F(X), a kind of T-surrogate, as follows. Represent X as a block of bits: X = t^3 + t^2 + 1 --> 1101. For each pair of 1 bits, accumulate the product (using xor), into a total. This total is F(X). In the example, the terms to be xored are 1000 * 1, 100 * 1, and 1000 * 100. The total is 101100. (Representing t^5 + t^3 + t^2.) Then it appears that X * Y = (X&Y)^2 + F(XvY) + F(X&Y) + F(X&~Y) + F(Y&~X). The logic operators & v ~ are to be used on right-justified bit patterns. The squaring operation is fast in GF2, simply spread out the bits, interleaving with 0s. (Squaring is a linear operator in GF2.) Has anyone seen anything like this? Rich

5 6

[math-fun] Wanted: an _inefficient_ number representation
by Steve Witham 30 Jun '06

30 Jun '06

>From: Henry Baker <hbaker1(a)pipeline.com> > >The length of a unary representation of n is O(n), while the >length of a positional representation of n is O(log(n)). > >Are there representations of n that grow as O(sqrt(n)) or O(cbrt(n)) ? The examples given by Joshua Zucker and Richard Guy are in funky bases ("base triangle" and base j(j+1)/2) that are between unary representation and positional representation. For binary, using histogram-of-lengths notation, a simple O(sqrt(n)) code is 0. 0 1 2 3 4 5 6... Meaning the code words are 00, 010, 011, 1000, 1001, 1010, 10101, 10110, 10111, 11000, 110010, 110011, 110100, 110101, 110110... Because 1/4 + 2/8 + 3/16 + 4/32 + 5/64... = 1 I found this not by smarts but by feeding 1 / 2 ^ sqrt(n) weights into my Huffman code histogram generator. It put out: 0. 0 0 2 4 6 8 10... Which is more efficient (fair) for that set of probabilities but not as cute. For 1 / 2 ^ cbrt( n ) it says: 0. 0 0 0 0 2 10 24 44 70 102 140 184 234 290... Which is ( 3 n^2 - n ) / 2^(n+4) for n = 1... So Huffman's algorithm is a way to turn an arbitrary expression into a series that adds up to 1. Including rootary binaries. --Steve

1 0

RE: [math-fun] Re: genetics-fun question -- another one
by Cordwell, William R 29 Jun '06

29 Jun '06

Well, 800 years divided by, say, 20 years/generation would give 40 generations. 2^40 (for example) is a large number, but, of course, this neglects all real-world factors such as breeding with distant relatives, geographic constraints, etc. Realistically, 5% sounds quite large, to me. Bill C. -----Original Message----- From: math-fun-bounces+cordwell=sandia.gov(a)mailman.xmission.com [mailto:math-fun-bounces+cordwell=sandia.gov@mailman.xmission.com] On Behalf Of franktaw(a)netscape.net Sent: Thursday, June 29, 2006 3:13 PM To: math-fun(a)mailman.xmission.com Subject: Re: [math-fun] Re: genetics-fun question -- another one Three comments (basically agreeing with Dan): Yes, random theory would show that _someone_ would end up with a large number of descendants. It would also show that it would very likely be somebody with a lot of offspring. Second, "Genghis Khan or his brothers" means that his _parents_ are the ones from whom 5% of the population derives. Third, without working out the numbers, I don't think it has been long enough since Genghis' time for it to be likely that anybody living at that time is the ancestor of 5% of the world's population. Franklin T. Adams-Watters -----Original Message----- From: dasimov(a)earthlink.net Henry wrote: << Do a Google search on Genghis Khan. Recent results claim that 5% of the world's population derives from him or his brothers. (The media claim that this is due to his large sexual appetite; while this probably helped, the truth is that random theory would show that _someone_ would end up with a large number of descendants. >> Right. That's totally plausible. The fact the Genghis Khan was both the most powerful and well-traveled person of his era just "probably helped". But mainly it's just a coincidence. Right. --Dan _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

RE: [math-fun] Re: genetics-fun question -- another one
by Henry Baker 29 Jun '06

29 Jun '06

It definitely helps to have a large number of direct descendants. But it is no guarantee -- I would imagine that entire families were wiped out at Pompeii, for example, or more recently in the tsunami. Spreading your descendants at great distances provides lots of backups. And it also helps to be on the winning side in a conquest, like the Khans. But the biggest effect is "compound interest", a la Fibonacci's rabbits. I sure hope that a lot of us are descendants of Fibonacci. It would be great justice for him. At 01:49 PM 6/29/2006, dasimov(a)earthlink.net wrote: >Henry wrote: > ><< >Do a Google search on Genghis Khan. >Recent results claim that 5% of the world's population derives from him or >his brothers. (The media claim that this is due to his large sexual appetite; >while this probably helped, the truth is that random theory would show that >_someone_ would end up with a large number of descendants. >>> > >Right. That's totally plausible. The fact the Genghis Khan was both the most >powerful and well-traveled person of his era just "probably helped". But mainly >it's just a coincidence. Right. > >--Dan

1 0

RE: [math-fun] Re: genetics-fun question -- another one
by dasimov＠earthlink.net 29 Jun '06

29 Jun '06

Henry wrote: << Do a Google search on Genghis Khan. Recent results claim that 5% of the world's population derives from him or his brothers. (The media claim that this is due to his large sexual appetite; while this probably helped, the truth is that random theory would show that _someone_ would end up with a large number of descendants. >> Right. That's totally plausible. The fact the Genghis Khan was both the most powerful and well-traveled person of his era just "probably helped". But mainly it's just a coincidence. Right. --Dan

2 1

Re: [math-fun] Re: genetics-fun question -- another one
by Henry Baker 29 Jun '06

29 Jun '06

My wife recently found that she has American Indian blood. We're now investigating the possibility of opening a casino. :-) At 11:43 AM 6/29/2006, Mike Stay wrote: >On 6/29/06, Tom Knight <tk(a)csail.mit.edu> wrote: >>They are busy doing exactly this in Iceland, where the genealogies are >>carefully recorded. Needless to say, there are many embarrassing >>revelations. I'm not sure this would ever be allowed politically. >>There is >>too much to be lost by too many people and cultures. Imagine what the >>reaction to Hitler's jewishness would have been, for example. > >A Maori friend of mine told a story of a large family reunion he >attended; they invited all the descendents of a great-grandfather, and >one white family that showed up was horrified to learn that they had >Maori ancestors. They demanded that their family name be taken off >the large family tree that had been set up and left in a huff. >Fortunately, no one else was offended in return; the other families >thought they were being ridiculous and had a good laugh. >-- >Mike Stay >metaweta(a)gmail.com >http://math.ucr.edu/~mike

1 0

RE: [math-fun] Re: genetics-fun question -- another one
by Henry Baker 29 Jun '06

29 Jun '06

Rich, et al: This is an area of very active research. Do a Google search on Genghis Khan. Recent results claim that 5% of the world's population derives from him or his brothers. (The media claim that this is due to his large sexual appetite; while this probably helped, the truth is that random theory would show that _someone_ would end up with a large number of descendants. A line either dies out within a few generations, or ends up with a huge population; it's actually quite difficult to have only a few descendants for a large number of generations.) Also see David MacKay's (info/coding theorist @ Cambridge) chapter called "Why have Sex? Information Acquisition and Evolution" in his book on Information Theory. MacKay claims that asexual reproduction yields approx 1 bit per generation due to survival of the fittest, whereas sexual reproduction (with exchange of genes) can yield up to sqrt(G) bits, where G is the total number of bits in the genome. (Human genome is 4-6x10^9 ~ 2^32; and you always wondered what was magic about a 32-bit word...) Note that mitochondrial dna is essentially asexual reproduction, which explains why this dna is reasonably stable from generation to generation. The chapter is on the web below, and in fact, his whole book is available for downloading. http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/265.280.pdf http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521642981 Math-funner Tom Knight is also hacking genetics these days -- perhaps he has some comments. At 10:03 AM 6/29/2006, Schroeppel, Richard wrote: >I have a puzzle from c. 1970. >Back then, it was science fiction, but now it looks less farfetched. >Suppose we have a big computer with everyone's genome data. >[Looking less farfetched every day, in fact.] >What can we deduce about the genomes of our ancestors? >Could we reconstruct an estimated genome of Fermat, Buddha, or Caesar? >There's some information loss from generation to generation: >Parents with N children will (on average) omit 2^-N of their >genes from (the set of) their children. Some of that lost information >could be deduced from knowing genomes of cousins (-> aunts & uncles -> >grandparents), so it's hard to see exactly how much is erased. >If we throw in present-day location information, we can probably >figure our who moved where, when, and perhaps deduce population >movements from long ago. > >Rich > >-----Original Message----- >From: math-fun-bounces+rschroe=sandia.gov(a)mailman.xmission.com on behalf of James Propp >Sent: Thu 6/29/2006 10:29 AM >To: math-fun(a)mailman.xmission.com >Subject: [math-fun] Re: genetics-fun question > >>So figuring out who's mother and who's daughter is as easy as labelling >>their genomes a,b and c,d and noticing which of them has the property >>that, eg, ccccccccccccc is the same as aaaabbbaabbbb. > >Neat! (And not even all that subtle; if I'd thought a bit harder about >what I supposedly learned in high school, I could've figured it out.) > >This fact about the asymmetry of the parent-child relationship suggests >a more general question: How much can you deduce about the precise way >in which two blood-relatives are related simply from looking at their >genes? > >This can be a real-world issue ("And is it your sworn testimony before >this court, as an expert in the field of genetics, that this man cannot >possibly be the nephew of Howard Hughes?"), but I could imagine it also >giving rise to some mathematically amusing albeit unrealistic puzzles >("Assume an infinite genome..."). Michael? > >Jim

2 1

[math-fun] genetics-fun question
by James Propp 29 Jun '06

29 Jun '06

If you had access to two cells --- one from a woman and one from her daughter --- would you be able to tell which was the mother and which was the daughter? For purposes of this question, you are NOT allowed to use markers of the biological age of the two individuals. What I want to know is whether, above and beyond the fact that A has as many genes in common with B as B has with A, there might be some subtle asymmetry in the genetic inheritance process that would let you figure out which one gave the genes to the other. This isn't really a math-fun question, but it seems close in spirit. Besides, math-funster Michael Kleber is sure to know the answer. (And I don't belong to any recreational genetics discussion forums.) Jim Propp

2 1

[math-fun] Binary codes as binary numbers
by Steve Witham 28 Jun '06

28 Jun '06

A nice way to look at and compare the binary codes we've been talking about is as binary representations (!) of the number one. This corresponds to a histogram of lengths of codewords. The most trivial code is for an alphabet of one symbol, whose probability is 1. I'll write it like this: 1. The other reading of that is, there is one symbol that encodes with no bits. (The question of how do you know how many of this symbol have been transmitted is outside the scope of everything we've been talking about!) It probably seems strange to include the zero as a possible length of codes, but I had an influential boss who said always to handle the zero case. Unary means zero or more zero bits followed by a one bit (or, zero or more one bits followed by a zero): 0. 1 1 1 1 1... The codes are 1, 01, 001, 0001, etc., in other words, one code of every length starting at 1. The binary interpretation is 0/1 + 1/2 + 1/4 + 1/8 + 1/16... = 1 Eight-bit binary has 256 symbols that use eight bits each: 0. 0 0 0 0 0 0 0 256 Ternary uses three combinations of two bits as digits and one as a terminator, so the lengths are always even: 0. 0 1 0 3 0 9 0 27 0 81 0 243... "Septary" or radix seven uses groups of three bits: 0. 0 0 1 0 0 7 0 0 49 0 0 343... Fibonacci or Zeckendorf coding is very interesting written this way: 0. 0 1 1 2 3 5 8 13 21 34 55 89... This works because 1/4 + 1/8 + 2/16 + 3/32 + 5/64 + 8/128 ... = 1. Ternary and septary are lumpy and Fibonacci is smooth--just looking at this you can guess that Fibonacci is more efficient with small numbers. Here are the optimal codes for Zipfian distributions over alphabets of 3, 15, 255 and 65535 symbols: 0. 1 2 0. 0 1 2 4 8 0. 0 0 1 2 4 8 16 32 64 128 In general the optimal encoding looks like that when the size of the alphabet is 2^(2^n) - 1. The awful combination code I talked about the other day uses n zero bits, n bits to tell the number of data bits ("exponent"), then the data bits ("mantissa"), so, e.g., the number 9 codes as 000 100 1001. 0. 0 0 1 0 0 2 4 0 0 8 16 32... This lumpy duckling doesn't even make use of all the available codes, so it doesn't add up to 1. But, it's the first code in this message that approaches 100% swanlike efficiency. Henry Baker (earlier than that) tested a combination of Fibonacci for the size, plus binary mantissa with the leading one removed: 0. 0 0 1 0 2 0 4 8 0 16 32 64... One way to smooth this out would be to (roughly) subtract the size of the size from the size: 0. 0 0 1 1 1 2 2 4 8 8 16 32... (The Fibonacci there is (1) (1) (1 2) (2 4 8) (8 16 32 64 128)...) These three combination codes all have runs of doublings that are interrupted exponentially less and less often, which is why they approach 100% efficiency. I imagine a code where the interruptions slowed more slowly would also work. Also, I've been trying codes where the uplings gradually approach doublings, e.g., 0. 0 1 2 1 3 4 6 11 16 27 45 76... This histogram representation can be used for coding and decoding, and as the output of a Huffman code generator. Codes generated this way end up with different bit patterns than Huffman generates (they're sorted instead of scrambled), but the efficiencies of the codes are the same. --Steve

3 3

RE: [math-fun] x^n + y^n = z^n + w^n
by dasimov＠earthlink.net 27 Jun '06

27 Jun '06

Of course, Beal's conjecture (for which there is now a prize of U.S.$100,000 for a proof OR a counterexample) goes as follows: BEAL'S CONJECTURE: If A^K +B^L = C^M , where A, B, C, K, L, M are positive integers, and K, L, M are all greater than 2, then A, B, and C must have a common prime factor. Based on recently-discussed equations for which no examples have ever been found, can Beal's conjecture reasonably be extended? In fact, what is the largest such conjecture that's consistent with what's known? --Dan

4 6