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

Re: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ?
by Henry Baker 03 Jul '17

03 Jul '17

If you have high speed raster graphics hardware, you may already have the capability for 2D transpose. There's also the famous (at least in computer graphics circles) "three shears" algorithm for image rotation by 90 degrees without any loss of information: 1. Shear the image 45 degrees to the right. 2. Shear the image 90 degrees down. 3. Shear the image 45 degrees to the left. The problem is that step #2 is usually just as hard in most memory systems as transposition, unless the hardware is set up to pick up word slices -- e.g., give me the 13th bit each of 32 words arranged as a 32-bit word. At 01:10 PM 7/2/2017, rcs(a)xmission.com wrote: >Transposition can be done in log2(N) passes over the matrix. >Imagine cutting your matrix into quarters, and exchanging the upper right >quarter with the lower left quarter. Next, do the same thing within each >quarter. Etc. If N isn't a power of 2, you may have to round it up; unsure. > >Rich > >----- >Quoting Henry Baker <hbaker1(a)pipeline.com>: >>Thanks, Adam. >> >>I'm already doing some of what you suggest. >> >>Is there any cleverness for *transposing* such bit matrices ? >> >>(As an aside, do *least squares* have any relevance over GF(2)?) >> >>Note that Gaussian elimination on extremely long vectors (much >>longer than the rank of the system) is faster if you invert the >>small square (rank x rank) matrix by itself, and then propagate that >> info to the rest of each row. >> >>Is there any cleverness that might be achieved if one had access to >>a *polynomial* multiply (and/or divide) operation over GF(2)[x] ? I >> seem to recall that this sort of HW is finally starting to show up >>as a "carryless multiply" operation. >> >>At 11:06 AM 7/2/2017, Adam P. Goucher wrote: >>>Yes, if the matrix has <= 64 rows, then you can store the columns as >>>64-bit integers and perform column operations using bitwise XOR. Also, >>>you can determine the uppermost and lowermost non-zero elements in a >>>column using the __builtin_clzll() instruction and variants thereof. >>> >>>This generalises, of course; with N rows, you can store each column >>>as a vector of ceil(N/64) 64-bit integers and perform column operations >>>with as many instructions. With SIMD, you can actually get away with as >>>few as ceil(N/256) instructions per column operation. >>> >>>The fact that there's only one non-zero element of GF(2) is also >>>helpful since there's no need to multiply the columns -- add/subtract >>>(i.e. XOR) is the only operation you ever need to perform! >>> >>>I'm using exactly this procedure in my PhD research on topological data >>>analysis. In particular, computing the persistent homology barcode from >>>the boundary map is (a slightly modified version of) Gaussian elimination >>>over GF(2). >>> >>>Best wishes, >>> >>>Adam P. Goucher >>> >>>>Sent: Sunday, July 02, 2017 at 6:29 PM >>>>From: "Henry Baker" <hbaker1(a)pipeline.com> >>>>To: math-fun(a)mailman.xmission.com >>>>Subject: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ? >>>> >>>>Other than Strassen? >>>> >>>>I.e., are there any bit-twiddling hacks that are particular to >>>>GF(2) for Gaussian elimination?

2 1

[math-fun] Exploding the myths of Ada Lovelace's mathematics
by Henry Baker 03 Jul '17

03 Jul '17

FYI -- None of the links below are behind paywalls. https://www.maths.ox.ac.uk/node/25695 Exploding the myths of Ada Lovelace's mathematics Ada Lovelace (1815â1852) is celebrated as "the first programmer" for her remarkable 1843 paper which explained Charles Babbage's designs for a mechanical computer. New research reinforces the view that she was a gifted, perceptive and knowledgeable mathematician. Christopher Hollings and Ursula Martin of Oxford Mathematics, and Adrian Rice, of Randolph-Macon College in Virginia, are the first historians of mathematics to investigate the extensive archives of the Lovelace-Byron family, held in Oxford's Bodleian Library. In two recent papers in the Journal of the British Society for the History of Mathematics and in Historia Mathematica they study Lovelace's childhood education, where her passion for mathematics was complemented by an interest in machinery and wide scientific reading; and her remarkable two-year "correspondence course" on calculus with the eminent mathematician Augustus De Morgan, who introduced her to cutting edge research on the nature of algebra. The work challenges widespread claims that Lovelace's mathematical abilities were more "poetical" than practical, or indeed that her knowledge was so limited that Babbage himself was likely to have been the author of the paper that bears her name. The authors pinpoint Lovelace's keen eye for detail, fascination with big questions, and flair for deep insights, which enabled her to challenge some deep assumptions in her teacher's work. They suggest that her ambition, in time, to do significant mathematical research was entirely credible, though sadly curtailed by her ill-health and early death. The papers, and the correspondence with De Morgan, can be read in full on the website of the Clay Mathematics Institute, who supported the work, as did the UK Engineering and Physical Sciences Research Council. http://www.sciencedirect.com/science/article/pii/S0315086017300319 The LovelaceâDe Morgan mathematical correspondence: A critical re-appraisal Christopher Hollings, Ursula Martin, Adrian Rice Available online 9 May 2017 Abstract Ada Lovelace is widely regarded as an early pioneer of computer science, due to an 1843 paper about Charles Babbage's Analytical Engine, which, had it been built, would have been a general-purpose computer. However, there has been considerable disagreement among scholars as to her mathematical proficiency. This paper presents the first account by historians of mathematics of the correspondence between Lovelace and the mathematician Augustus De Morgan from 1840â41. Detailed contextual analysis allows us to present a corrected ordering of the archive material, countering previous claims of Lovelace's mathematical inadequacies, and presenting a more nuanced assessment of her abilities. http://www.tandfonline.com/doi/pdf/10.1080/17498430.2017.1325297 The early mathematical education of Ada Lovelace Christopher Hollings, Ursula Martin & Adrian Rice To cite this article: Christopher Hollings, Ursula Martin & Adrian Rice (2017): The early mathematical education of Ada Lovelace, BSHM Bulletin: Journal of the British Society for the History of Mathematics, DOI: 10.1080/17498430.2017.1325297 CHRISTOPHER HOLLINGS and URSULA MARTIN University of Oxford, UK ADRIAN RICE Randolph-Macon College, USA Ada, Countess of Lovelace, is remembered for a paper published in 1843, which translated and considerably extended an article about the unbuilt Analytical Engine, a general-purpose computer designed by the mathematician and inventor Charles Babbage. Her substantial appendices, nearly twice the length of the original work, contain an account of the principles of the machine, along with a table often described as 'the first computer program'. In this paper we look at Lovelace's education before 1840, which encompassed older traditions of practical geometry; newer textbooks influenced by continental approaches; wide reading; and a fascination with machinery. We also challenge judgements by Dorothy Stein and by Doron Swade of Lovelace's mathematical knowledge and skills before 1840, which have impacted later scholarly and popular discourse.

1 0

Re: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ?
by Henry Baker 02 Jul '17

02 Jul '17

The 3 shears procedure is more exactly: 1. Shear the bitmap horizontally 45 degrees to the right; the X-axis stays the same, the Y-axis tilts 45 degrees to the right. 2. Shear the bitmap vertically 45 degrees down; the Y-axis drops down 45 degrees to horizontal, the X-axis drops down 45 degrees below horizontal. 3. Shear the bitmap horizontally 45 degrees to the left; the Y-axis remains horizontal, the X-axis shifts 45 degrees to become vertical. At 01:51 PM 7/2/2017, Henry Baker wrote: >If you have high speed raster graphics hardware, you may already have the capability for 2D transpose. > >There's also the famous (at least in computer graphics circles) "three shears" algorithm for image rotation by 90 degrees without any loss of information: > >1. Shear the image 45 degrees to the right. >2. Shear the image 90 degrees down. >3. Shear the image 45 degrees to the left. > >The problem is that step #2 is usually just as hard in most memory systems as transposition, unless the hardware is set up to pick up word slices -- e.g., give me the 13th bit each of 32 words arranged as a 32-bit word. > >At 01:10 PM 7/2/2017, rcs(a)xmission.com wrote: >>Transposition can be done in log2(N) passes over the matrix. >>Imagine cutting your matrix into quarters, and exchanging the upper right >>quarter with the lower left quarter. Next, do the same thing within each >>quarter. Etc. If N isn't a power of 2, you may have to round it up; unsure. >> >>Rich >> >>----- >>Quoting Henry Baker <hbaker1(a)pipeline.com>: >>>Thanks, Adam. >>> >>>I'm already doing some of what you suggest. >>> >>>Is there any cleverness for *transposing* such bit matrices ? >>> >>>(As an aside, do *least squares* have any relevance over GF(2)?) >>> >>>Note that Gaussian elimination on extremely long vectors (much >>>longer than the rank of the system) is faster if you invert the >>>small square (rank x rank) matrix by itself, and then propagate that >>> info to the rest of each row. >>> >>>Is there any cleverness that might be achieved if one had access to >>>a *polynomial* multiply (and/or divide) operation over GF(2)[x] ? I >>> seem to recall that this sort of HW is finally starting to show up >>>as a "carryless multiply" operation. >>> >>>At 11:06 AM 7/2/2017, Adam P. Goucher wrote: >>>>Yes, if the matrix has <= 64 rows, then you can store the columns as >>>>64-bit integers and perform column operations using bitwise XOR. Also, >>>>you can determine the uppermost and lowermost non-zero elements in a >>>>column using the __builtin_clzll() instruction and variants thereof. >>>> >>>>This generalises, of course; with N rows, you can store each column >>>>as a vector of ceil(N/64) 64-bit integers and perform column operations >>>>with as many instructions. With SIMD, you can actually get away with as >>>>few as ceil(N/256) instructions per column operation. >>>> >>>>The fact that there's only one non-zero element of GF(2) is also >>>>helpful since there's no need to multiply the columns -- add/subtract >>>>(i.e. XOR) is the only operation you ever need to perform! >>>> >>>>I'm using exactly this procedure in my PhD research on topological data >>>>analysis. In particular, computing the persistent homology barcode from >>>>the boundary map is (a slightly modified version of) Gaussian elimination >>>>over GF(2). >>>> >>>>Best wishes, >>>> >>>>Adam P. Goucher >>>> >>>>>Sent: Sunday, July 02, 2017 at 6:29 PM >>>>>From: "Henry Baker" <hbaker1(a)pipeline.com> >>>>>To: math-fun(a)mailman.xmission.com >>>>>Subject: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ? >>>>> >>>>>Other than Strassen? >>>>> >>>>>I.e., are there any bit-twiddling hacks that are particular to >>>>>GF(2) for Gaussian elimination?

1 0

Re: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ?
by Henry Baker 02 Jul '17

02 Jul '17

Thanks, Adam. I'm already doing some of what you suggest. Is there any cleverness for *transposing* such bit matrices ? (As an aside, do *least squares* have any relevance over GF(2)?) Note that Gaussian elimination on extremely long vectors (much longer than the rank of the system) is faster if you invert the small square (rank x rank) matrix by itself, and then propagate that info to the rest of each row. Is there any cleverness that might be achieved if one had access to a *polynomial* multiply (and/or divide) operation over GF(2)[x] ? I seem to recall that this sort of HW is finally starting to show up as a "carryless multiply" operation. At 11:06 AM 7/2/2017, Adam P. Goucher wrote: >Yes, if the matrix has <= 64 rows, then you can store the columns as >64-bit integers and perform column operations using bitwise XOR. Also, >you can determine the uppermost and lowermost non-zero elements in a >column using the __builtin_clzll() instruction and variants thereof. > >This generalises, of course; with N rows, you can store each column >as a vector of ceil(N/64) 64-bit integers and perform column operations >with as many instructions. With SIMD, you can actually get away with as >few as ceil(N/256) instructions per column operation. > >The fact that there's only one non-zero element of GF(2) is also >helpful since there's no need to multiply the columns -- add/subtract >(i.e. XOR) is the only operation you ever need to perform! > >I'm using exactly this procedure in my PhD research on topological data >analysis. In particular, computing the persistent homology barcode from >the boundary map is (a slightly modified version of) Gaussian elimination >over GF(2). > >Best wishes, > >Adam P. Goucher > >> Sent: Sunday, July 02, 2017 at 6:29 PM >> From: "Henry Baker" <hbaker1(a)pipeline.com> >> To: math-fun(a)mailman.xmission.com >> Subject: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ? >> >> Other than Strassen? >> >> I.e., are there any bit-twiddling hacks that are particular to GF(2) for Gaussian elimination?

1 0

[math-fun] Any cool hacks for Gaussian elimination over GF(2) ?
by Henry Baker 02 Jul '17

02 Jul '17

Other than Strassen? I.e., are there any bit-twiddling hacks that are particular to GF(2) for Gaussian elimination?

2 1

Re: [math-fun] Equal sums of powers
by Dan Asimov 02 Jul '17

02 Jul '17

<< Prouhet's Thue-Morse based solution turns out to be ... Solution to what? —Dan

2 1

[math-fun] Unfolding questions
by David Wilson 01 Jul '17

01 Jul '17

1. For a given polyhedron, what is the minimal number edges that need to be cut to unfold it into a connected planar surface? For example, 3 edges are necessary for a tetrahedron, I think 7 for a cube. 2. Is this minimal number a function of the number of faces, edges and vertices of the polyhedron? 3. Is this minimal number unique? Does any unfolding of the same polyhedron have the same number of edge cuts? 4. If (3) is false, is there a polyhedron where some unfolding has more edge cuts, but shorter total edge cut length, than some other unfolding? 5. Is there a convex polyhedron for which some unfolding exhibits overlapping faces in the plane? If so, what is the smallest number of faces on such a polyhedron?

9 19

[math-fun] Philip Yasskin wants to know
by James Propp 27 Jun '17

27 Jun '17

Philip Yasskin of Texas A&M taught me a fun game yesterday. (He learned it from his son, who learned it at a Renaissance Faire.) You roll a die, and the number it shows becomes the current score. The first player then rotates the die by 90 degrees, so that one of the four faces adjacent to the old top face becomes the new top face. The score increases by this amount. The second player does the same. Play alternates in this fashion until either the score becomes exactly 31 (in which case the player who just played wins) or the score exceeds 31 (in which case the player who just played loses). In some ways it's more natural to look at the "score deficit" (31 minus the score) as opposed to the score, especially if one wants to consider other versions of the game in which some number other than 31 is the "target". Philip noticed that when you look at the behavior of the game as a function of the score-deficit, you observe periodicity with period 9 (maybe he said "eventual periodicity" --- I forget), and he wondered why the 9 shows up. Here's a proposed variant that might shed light on Philip's question (or might further enlarge the darkness). For each k, we can consider a combinatorial game whose states are specified by ordered pairs (n,i), where n is a non-negative integer and i is between 1 and 2k inclusive. (For concreteness you might want to focus on k=3, and to think of i as the number shown on the top face of a 6-sided die.) A legal move goes from (n,i) to (n-j,j) as long as n-j is non-negative and j is neither i nor 2n+1-i. (For our concrete case k=3, j can be any number that is adjacent to i on the die.) Does this game exhibit eventual periodicity with period 3k for all values of k? That is, can we say that (n,i) is a P-position iff (n-3k,i) is, for all sufficiently large n? Jim Propp

2 2

[math-fun] discrete log in reducible polynomials over GF(2) ??
by Henry Baker 25 Jun '17

25 Jun '17

This question is related to CRC polynomials, so the degree of the polynomials I'm (currently) concerned with are on the order of 32 -- i.e., far too small for crypto applications. The coefficients are 0's and 1's; denote the coefficient field F2 with elements {0,1}. Consider the polynomials in "x" over F2, i.e., F2[x]. Suppose we have a fixed polynomial p(x) in F2[x] of degree n, where n is in the approximate range of 32. We will work in the ring F2[x]/p(x), whose representatives will be the remainders of polynomials f(x) in F2[x] after division by p(x). Clearly, if r(x) is such a remainder, degree(r(x))<degree(p(x))=n. Now consider the multiplicative group generated by x itself in the ring F2[x]/p(x). We will **NOT** assume that p(x) is irreducible, so F2[x]/p(x) is not necessarily a finite field, and x may not generate the complete multiplicative group of F2[x]/p(x). I'd like to compute logarithms base x in this ring -- i.e., given the representative for the ring element x^i, I'd like to efficiently compute i. Is there any non-table-lookup method or any non-linear-search method for computing this discrete log? What about when p(x) IS irreducible -- i.e., F2[x]/p(x) really is a finite *field* ? BTW, since 32 is reasonably small, I'm willing to do a lot of precomputation; I just don't want to have to store a large table, and I'd love the final algorithm to be extremely fast.

1 1

[math-fun] Find a function ...
by Guy Haworth 24 Jun '17

24 Jun '17

My college magazine includes this challenge: Find a function f(x) such that for every real x not equal to 0 or 1, we have f(1/x) + f(1-x) = x It's from Oxford BNC's Konstantin Ardakov. I guess there's a clue here that 1/x and 1/(1-x) feature in the solution ... but how does one go about this? Guy

3 2