May 2006 - mathfun@mailman.xmission.com

[math-fun] Gauss-Seidel considered a pile of wombat's do's
by Fred lunnon 21 May '06

21 May '06

I've been looking at animating the motion of some (rather nonstandard) robots: this involves interpreting the kinematic constraints as a bunch of simultaneous polynomial equations in several (7) variables with nullity 1, then tracing the motion path via continuous solution of the equations as a function of the time parameter. If possible, I want to solve these in real time --- i.e. fast enough to keep pace with the graphical display (say 30 frames per second). The classical Adams-Bashforth-Moulton (predictor-corrector) method for numerical solution of a differential equation seems a suitable vehicle for the task: the third order version costs only 2 iterations for acceptable accuracy. [For some reason I had thought first of Runge-Kutta-Merson, which however requires the differentials to be available as an explicit function of time.] To cast the motion equations as an ODE system, they must be differentiated and the resulting linear equations for the derivatives solved --- in practice numerically, at each step. Now, we already have to hand an approximate solution to these linear equations --- the derivatives at the previous step --- so an iterative algorithm looks worth trying. The textbook method is Gauss-Seidel, which (with luck, and a diagonally dominant matrix) converges geometrically. I have to admit I was already prejudiced; and after spending an evening establishing how cumbersome and ineffective this idea proves to be [at any rate, in this application], in desperation I cooked up a home-grown alternative. It's a matrix variation of an old trick assembly-coders used in the days before hardware division: starting from an approximation b to 1/a, iterate b := 2 b - a b^2. In the matrix context this becomes simply B := 2 B - B A B. It's easy to show that if I - A B = D, then for the next iterate B' we have I - A B' = D^2; so provided the spectral radius (maximum eigenvalue modulus) of D is d < 1, the algorithm converges and is second-order. If A is rectangular or singular, it converges instead to the Moore-Penrose pseudo-inverse. This is dead simple to program, and fast --- 2 iterations suffice for the application. Admittedly it is still slightly slower (maybe 25%) than solving the equations directly; though if matrix multiplication were hardwired --- as already in some graphics accelerators --- it might well be faster. Yet I don't recall ever seeing it mentioned in print --- can anybody out there enlighten me? To use it for matrix inversion in general, we'd need to construct an initial approximation B for which d < 1. This unfortunately looks nontrivial. [In the original real number context, it was worked around using the fact that binary representation gives an easy approx. base 2 log; and for reduced a ~ 1 we can just choose b = 1.] Fred Lunnon

2 4

Re: [math-fun] Gauss-Seidel considered a pile of wombat's do's
by Henry Baker 21 May '06

21 May '06

At 03:39 PM 5/20/2006, Fred lunnon wrote: Suppose instead we modify it to the more amenable > B := A; B := (B + B^{+T})/2 >(average B with its transposed pseudo-inverse). For real nonsingular >square A, the result appears to converge to an orthogonal matrix B >such that A = B C with C symmetric: the "polar decomposition" of A. >Presumably this must be well-known; but oddly it doesn't seem to be >mentioned in in Higham et al ... This iteration is well-known in the graphics community. I don't know whether it is covered in "Graphics Gems" or not. The graphics and robotics communities have been pushing certain areas of matix algebra (at least for small matrices -- up to 4x4, 5x5, etc.) really, really hard. The classic matrix math books don't seem to have kept up...

1 0

Re: [math-fun] big numbers and how they're made (fwd)
by Richard Guy 19 May '06

19 May '06

Others besides Thane may be interested in this Joe Gallian message. R. ---------- Forwarded message ---------- Date: Thu, 18 May 2006 19:05:00 -0500 From: jgallian <jgallian(a)d.umn.edu> To: thane(a)best.com Cc: Richard Guy <rkg(a)cpsc.ucalgary.ca> Subject: Re: [math-fun] big numbers and how they're made Thane, UPS has simple system based on modulo 7 arithmetic to detect errors. US currency does not use a check digit scheme. Euros use a mod 9 scheme. I will email you an article that explains many check digit schemes in use. Joe Gallian --On Thursday, May 18, 2006 3:26 PM -0600 Richard Guy <rkg(a)cpsc.ucalgary.ca> wrote: > Joe Gallian has an article or two about such things. R. > > On Wed, 17 May 2006, Thane Plambeck wrote: > >> I bought this book, "Identification Numbers and Check Digit Schemes" >> in the hopes that it would >> describe the ID number / checksum / hashing schemes actually used >> in some real applications. >> I'd like to give a talk on the subject to a general audience. >> >> http://www.amazon.com/gp/product/0883857200/104-8328046-6239112?v=gl >> ance&n=283155 >> >> However, this book left me unsatisfied. Ideally, I'd like to know, >> for example, how to distinguish between >> a valid UPS tracking number and an invalid one, or (say) a valid US >> twenty dollar bill serial number >> and an invalid one. >> >> UPS tracking#: 1Z9999999999999999 >> >> US $20 bill, Series 2004: EB 42994244 D >> >> Such schemes are presumably often proprietary / unpublished, for >> security reasons, although the >> "there is no security through obscurity" maxim would seem to apply. >> >> Googling hasn't turned up much, except in a few unsavory hacking >> resources (mostly how to forge >> a valid credit card number) >> >> Anyone know a good resource? >> >> >> >> -- >> Thane Plambeck >> http://www.plambeck.org/ehome.htm >> >> >> >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com >> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >>

1 0

[math-fun] big numbers and how they're made
by Thane Plambeck 19 May '06

19 May '06

I bought this book, "Identification Numbers and Check Digit Schemes" in the hopes that it would describe the ID number / checksum / hashing schemes actually used in some real applications. I'd like to give a talk on the subject to a general audience. http://www.amazon.com/gp/product/0883857200/104-8328046-6239112?v=glance&n=… However, this book left me unsatisfied. Ideally, I'd like to know, for example, how to distinguish between a valid UPS tracking number and an invalid one, or (say) a valid US twenty dollar bill serial number and an invalid one. UPS tracking#: 1Z9999999999999999 US $20 bill, Series 2004: EB 42994244 D Such schemes are presumably often proprietary / unpublished, for security reasons, although the "there is no security through obscurity" maxim would seem to apply. Googling hasn't turned up much, except in a few unsavory hacking resources (mostly how to forge a valid credit card number) Anyone know a good resource? -- Thane Plambeck http://www.plambeck.org/ehome.htm

7 6

[math-fun] California Math Exit Exam
by Henry Baker 18 May '06

18 May '06

Here's another question to add to the California Exit Exam for high school students in mathematics: If there are 80 questions on this test, and each of the 80 questions has 4 choices, what is the probability that someone could pass (>= 55%) [oops, first answer the question of how many questions out of a total of 80 questions 55% is] the test, if for each question he chose one of the 4 answers at random (p=25% for each answer). Alternatively, assuming that the test preparers aren't insane, what is the probability that someone could pass the test by always choosing the "A" answer for each question? Extra credit: using this probability, estimate the number of times one should take the test to raise the probability of passing it at least once to 80%.

2 4

Re: [math-fun] big numbers and how they're made
by dasimov＠earthlink.net 18 May '06

18 May '06

Have you tried 2600 ? --Dan << I bought this book, "Identification Numbers and Check Digit Schemes" in the hopes that it would describe the ID number / checksum / hashing schemes actually used in some real applications. I'd like to give a talk on the subject to a general audience. http://www.amazon.com/gp/product/0883857200/104-8328046-6239112?v=glance&n=… However, this book left me unsatisfied. Ideally, I'd like to know, for example, how to distinguish between a valid UPS tracking number and an invalid one, or (say) a valid US twenty dollar bill serial number and an invalid one. UPS tracking#: 1Z9999999999999999 US $20 bill, Series 2004: EB 42994244 D Such schemes are presumably often proprietary / unpublished, for security reasons, although the "there is no security through obscurity" maxim would seem to apply. Googling hasn't turned up much, except in a few unsavory hacking resources (mostly how to forge a valid credit card number) Anyone know a good resource? >>

1 0

[math-fun] Don't hire authoritarian programmers
by R. William Gosper 17 May '06

17 May '06

This quick and not at all dirty one liner to draw an orthoscheme, block([o:[0,0,0],a:[1,0,0],b:[0,1,0],c:[0,1,1]],plotfaces(combinations([o,a,b,c],3))) was thwarted by the previous incarnation of this line of code in Macsyma\Macsyma2\share\set2 : /*if not %set=setify(%set) then "Some a&&hole thinks you should be screwed with error(\"First argument to subpowerset must be a set.)",*/ --rwg PS, It can't be news to serious sudokulists, but making the rounds of Mountain View High School is gosper.org/sud5.PNG, a quincunx of overlapping 9x9s with clues in four concentric rings.

4 5

RE: [math-fun] California Math Exit Exam
by dasimov＠earthlink.net 17 May '06

17 May '06

<< > The radius of the earth's orbit is 150,000,000,000 meters. What is > this number in scientific notation? > A 1.5x10^-11 > B 1.5x10^11 > C 15x10^10 > D 150x10^9 > > [The last time I looked, the Earth's orbit was ~ elliptical, so it > has a semimajor & semiminor axis...] B, C, and D are all correct. Is scientific notation supposed to be normalized, making B the only correct answer >> Yes, that's the way it's usually taught in school. --Dan

2 1

RE: [math-fun] California Math Exit Exam
by Marc LeBrun 16 May '06

16 May '06

>=Cordwell, William R > so a student with knowledge at only the 40% level (whatever that means) Speaking as a product of the California public school system myself: If it's indeed true, as I've heard, that the math portion only involves curriculum material at or below the 8th grade level, and the English at or below 10th grade level, then that means, let's see, 3rd or 4th grade level, right? Do I pass?

5 6

Re: [math-fun] California Math Exit Exam
by Henry Baker 16 May '06

16 May '06

I seem to recall someone once advertising butter by the "tub", but 45 gallons of butter would be a pretty big tub... Also 60 lbs of tea: http://www.new-york-lawyer.ws/law-dictionary/tribute.htm At 05:37 AM 5/16/2006, dasimov(a)earthlink.net wrote: >Don't people know that "tub" means a largish pail, not just a bathtub? > >--Dan

1 0