March 2018 - mathfun@mailman.xmission.com

[math-fun] Does this int seq have a name?
by Henry Baker 16 Mar '18

16 Mar '18

1,7,13,19,44,377,710,104703,... and another closely related sequence 1,6,19,25,44,333,710,103993,... They are both monotonically increasing. This posting should have been made on pi day. The sequences are related to CORDIC.

2 1

Re: [math-fun] XCT instruction
by Henry Baker 16 Mar '18

16 Mar '18

Problems with XCT (execute one instruction): * no clean/obvious semantics; semantics have to be worked out for each different instruction being "executed" * only one level of execute (at least for IBM) * originally used for *tables* of instructions, but what about variable-length instructions? (Similar problem to "skip" instructions) * what are the semantics in the case of interrupts? We now have architectures which support "virtual machines"; analogous problems at much larger scale. At 04:47 PM 3/15/2018, rcs(a)xmission.com wrote: >PS: Does anyone else miss the XCT instruction? The 7094 & PDP6/10 had >it, but it seems to have vanished. I guess it's an architectural >nightmare for the hardware folks. --Rich

7 9

Re: [math-fun] complex #'s explore circle group; quaternions explore SU(2) ?
by Dan Asimov 15 Mar '18

15 Mar '18

The unit quaternions, {x + yi + zj + wk | x^2 + y^2 + z^2 + w^2 = 1}, form the unit sphere S^3 in R^4, a 3-(real)-dimensional manifold. As an odd-dimensional manifold, S^3 is not likely to have a convenient parametrization by complex numbers, exactly, but as SU(2) of course we can write (a -b*) SU(2) = { ( ) in M_(2x2)(C)| |a|^2 + |b|^2 = 1} (b a*) But you probably knew that. I'm not sure of the exact meaning of "enumerated uniformly" here. Or what enumerated uniformly by a random walk means. But there is no differentiable map from a real 2-dimensional manifold, or from a complex 1-dimensional manifold, to S^3 that is *surjective*. (Proof: The non-critical points are carried to S^3 by a locally one-to-one map; the critical points are carried to a set of measure zero by Sard's Theorem.) The group SU(2) is the double cover of the orientation-presrving rotation group SO(3) of R^3. One can think of any element of SO(3) as defined by an ordered pair (a, theta) where a is the axis of counterclockwise rotation, and theta is an angle in the range (0, pi). Such a pair can be represented by the ball B = {(x,y,z) in R^3 | x^2 + y^2 + z^2 <= pi} where all points with theta = 0 have been identified to the origin. We still have each rotation by angle pi represented in B as a pair of antipodal points. So to get SO(3) we need to identify these pairs each to a single point. ----- There is a related question of finding a DENSE curve in some space: For any manifold M one may ask for a smooth (C^oo) curve that is dense in M. It's interesting to also require that the curve be *uniformly distrbuted* in M. Not a lot is known about that. But I do believe the probabilist Persi Diaconis has a number of theorems on the subject of how a random walk on a Lie group becomes dense. —Dan Henry Baker wrote: ----- We know that the circle group is enumerated uniformly by cos(t)+i*sin(t), for i in [0,2*pi) using a single (real) parameter t. Is there a way of uniformly enumerating the unit quaternions * with 1 parameter (probably some sort of random walk) ? * with 2 parameters (probably some sort of random walk) ? * with 1 complex parameter ????? * with 3 parameters ??? -----

1 0

[math-fun] Good video about Buffon without calculus
by James Propp 15 Mar '18

15 Mar '18

Does anyone know of a good video about the Buffon needle problem that includes the calculus-free proof via linearity of expectation? I just spent a few minutes on YouTube and found a couple of videos that went that route, but they didn’t do it in a clear way. (Jordan Ellenberg gives this proof in his book “How Not to Be Wrong”, but the laypeople I’ve spoken to about this part of his book found it hard to follow, so I think a lengthier explanation is required, especially one that includes visuals.) You would think that with all the hoopla about Pi Day, someone would have already made such a video! Jim Propp (PS: Hmm, “hoop”-la about Pi Day?)

1 0

Re: [math-fun] Wieferich #s
by Bill Gosper 15 Mar '18

15 Mar '18

On 2018-03-14 18:00, Gareth McCaughan wrote: > On 15/03/2018 00:44, Bill Gosper wrote: >> Ouch. http://www.chalcedon.demon.co.uk/rgep/psp-12.gz >> not there. Anybody good with archives? --Bill > > A bit of googling finds this > > http://s369624816.websitehome.co.uk/rgep/psp-12.gz > > but I cannot guarantee that it is what it appears to be. > > (It's linked from s369624816.websitehome.co.uk/rgep/carpsp.html > which looks like a copy of -- perhaps an old version of -- RGEP's > page on chalcedon.demon.co.uk.) Gareth, thanks! psp-13 is even better, consolidating his old -12 and -13. On 2018-03-13 15:47, rcs(a)xmission.com wrote: > I can show that it can only work for odd numbers :-). > > There are two directions to examine: > > a) Dig up Pinch's list of 2-pseudoprimes & try them. (Is there a bigger list?) Duh, thanks! In[5]:= Select[ToExpression@%1, PowerMod[2, #, #^2] == 2 &] // Timing Out[5]= {4.180282, {}} Compressing 2 days into 4 seconds. Check: In[6]:= Select[ToExpression[%1][[-9 ;; -1]], PowerMod[2, #, #^1] == 2 &] // Timing Out[6]= {0.237544, {9999327855061, 9999388511281, 9999501351841, 9999516745501, 9999540989059, 9999590518867, 9999899578441, 9999940201981, 9999946514845}} Meanwhile, in case Pinch missed something, the mindless program has slogged past 9.5G. > > b) Try using a base other than 2. > We know 2^341=2 (mod 341) with 341=11*31. > Find N from 2^341 = 2+341N (mod 341^2). > Then look at (2+341N)^341 and expand the first terms of the binomial ... > 2^341 + 341 * 2^340 * 341N + stuff*(341N)^2 > so (2+341N)^341 = 2^341 = 2+341N (mod 341^2). > This shows that the composite 341 has some base 2+341N that makes 341 a > "Wieferich pseudoprime". > If there are no base 2 WPSPs, it's probably just luck. > > Rich > > ----- Looks like time to conjecture that the primality condition is redundant. --rwg A list of length 2 but believed infinite. I love it. Sometimes it's really hard to pass up an Information Booth. But the guy ahead of me is probably asking for an odd perfect number. > Quoting Bill Gosper <billgosper(a)gmail.com>: >> Trying a few more, >> In[6]:= Select[Range[10^9], PowerMod[2, #, #^2] == 2 &] // tim >> >> During evaluation of In[6]:= 2031.078479,2 >> >> Out[6]= {1093, 3511} >> Rich? Anybody? Is it obvious this can only yield primes? Time to add the >> conjecture to A001220? --rwg >> >> On Mon, Mar 12, 2018 at 12:36 PM, Bill Gosper <billgosper(a)gmail.com> wrote: >> >>> https://oeis.org/A077816 , e.g., >>> In[19]:= Select[Range@9999, Mod[2^EulerPhi@#, #^2] == 1 &] >>> >>> Out[19]= {1093, 3279, 3511, 7651} >>> >>> A different definition might be >>> In[18]:= Select[Range@999999, Mod[2^#, #^2] == 2 &] >>> >>> Out[18]= {1093, 3511} >>> >>> No mention of primes! >>> https://oeis.org/A001220 >>> >>> Arthur Wieferich showed that if p is not a term of this sequence, then the >>> First Case of Fermat's Last Theorem has no solution in x, y and z for prime >>> exponent p (cf. Wieferich, 1909). - Felix Fröhlich >>> <https://oeis.org/wiki/User:Felix_Fröhlich>, May 27 2016 >>> >>> --rwg >>> >> _______________________________________________

1 0

Re: [math-fun] History of swap/exch computer instructions ?
by rcs＠xmission.com 14 Mar '18

14 Mar '18

[another mailing list flub --Rich] Date: Wed, 14 Mar 2018 15:11:56 -0400 Subject: Re: [math-fun] History of swap/exch computer instructions ? From: wba <wbackerman(a)gmail.com> To: math-fun(a)mailman.xmission.com, William Ackerman <wba(a)alum.mit.edu> This reminds me of another famous swapping hack, often used by bit-bumming assembly language hackers (such as myself). You want to swap two things--memory, register, whatever, and you have XOR instructions. You need to have XOR instructions that go both ways: if swapping a register with memory, you need instructions that can XOR a register out to memory. The 360, and Intel, being monstrously CISC machines, have them. I used this hack many times in my youth. A -->XOR--> B // That is, set B = A^B B -->XOR--> A A -->XOR--> B The 360 had "block XOR" instructions ("XORM"? Can't be bothered to look it up.) You could XOR one long block of memory onto another. So you could use this hack to swap two blocks of memory, without any temporaries. -------- On 03/14/2018 12:05 PM, Adam P. Goucher wrote: Maybe the reason for lacking ROTATEF in modern instruction sets is that the n-ary rotation can be implemented using (n-1) SWAP instructions: rotatef i_1 i_2 i_3 ... i_n <==> swap i_1 i_2 swap i_2 i_3 ... swap i_{n-1} i_n Best wishes, Adam P. Goucher

3 4

[math-fun] Wieferich #s
by Bill Gosper 14 Mar '18

14 Mar '18

Ouch. http://www.chalcedon.demon.co.uk/rgep/psp-12.gz not there. Anybody good with archives? --Bill I've found a soucecode of Macsyma's integer factorer. Instead of a simple table of pseudoprimes, there seems to be a table of one-parameter families. ? I've gone senile. --rwg On 2018-03-13 15:47, rcs(a)xmission.com wrote: > I can show that it can only work for odd numbers :-). > > There are two directions to examine: > > a) Dig up Pinch's list of 2-pseudoprimes & try them. (Is there a bigger list?) > > b) Try using a base other than 2. > We know 2^341=2 (mod 341) with 341=11*31. > Find N from 2^341 = 2+341N (mod 341^2). > Then look at (2+341N)^341 and expand the first terms of the binomial ... > 2^341 + 341 * 2^340 * 341N + stuff*(341N)^2 > so (2+341N)^341 = 2^341 = 2+341N (mod 341^2). > This shows that the composite 341 has some base 2+341N that makes 341 a > "Wieferich pseudoprime". > If there are no base 2 WPSPs, it's probably just luck. > > Rich > > ----- > Quoting Bill Gosper <billgosper(a)gmail.com>: >> Trying a few more, >> In[6]:= Select[Range[10^9], PowerMod[2, #, #^2] == 2 &] // tim >> >> During evaluation of In[6]:= 2031.078479,2 >> >> Out[6]= {1093, 3511} >> Rich? Anybody? Is it obvious this can only yield primes? Time to add the >> conjecture to A001220? --rwg >> >> On Mon, Mar 12, 2018 at 12:36 PM, Bill Gosper <billgosper(a)gmail.com> wrote: >> >>> https://oeis.org/A077816 , e.g., >>> In[19]:= Select[Range@9999, Mod[2^EulerPhi@#, #^2] == 1 &] >>> >>> Out[19]= {1093, 3279, 3511, 7651} >>> >>> A different definition might be >>> In[18]:= Select[Range@999999, Mod[2^#, #^2] == 2 &] >>> >>> Out[18]= {1093, 3511} >>> >>> No mention of primes! >>> https://oeis.org/A001220 >>> >>> Arthur Wieferich showed that if p is not a term of this sequence, then the >>> First Case of Fermat's Last Theorem has no solution in x, y and z for prime >>> exponent p (cf. Wieferich, 1909). - Felix Fröhlich >>> <https://oeis.org/wiki/User:Felix_Fröhlich>, May 27 2016 >>> >>> --rwg >>>

2 1

Re: [math-fun] History of swap/exch computer instructions ?
by Henry Baker 14 Mar '18

14 Mar '18

Yes, indeed, the 360 had a storage2storage ("SS") XOR instruction. Although "N", the number of bytes to XOR, was an 8-bit *constant* embedded into the instruction's 2nd byte, this *constant* could be modified as part of the "execute" "EX" instruction, as 8 bits of a register specified by the EX instruction were OR'd into the referenced XOR instruction's 2nd byte prior to execution. This combination EX/XOR allowed a variable-length storage2storage XOR at memory speeds. Some models -- e.g., 360/50 -- had memory alignment restrictions on the operands for various instructions, and some instructions weren't there at all (decimal ??), although they could be software-emulated after a unimplemented instruction trap. I don't recall whether this particular instruction was implemented on the stripped down 360 models, or whether XOR had memory alignment issues on these stripped down models. I seem to recall that even on the bigger 360's, these byte-oriented instructions weren't particularly fast, as they operated byte-for-byte instead of word-for-word. I don't recall how the 360 did interrupts, but it may have allowed a 255-byte XOR instruction to be interrupted in the middle and later resumed; thus, these types of XOR's were obviously NOT suitable for semaphores! It's possible that IBM included the XOR instruction for more than just its NSA customers; IBM used its own computers quite extensively internally for logic simulation. Also, many error-correcting codes based upon GF(2^k) were being used by all sorts of technical and commercial customers. At 12:51 PM 3/14/2018, rcs(a)xmission.com wrote: >[another mailing list flub --Rich] > >Date: Wed, 14 Mar 2018 15:11:56 -0400 >Subject: Re: [math-fun] History of swap/exch computer instructions ? >From: wba <wbackerman(a)gmail.com> >To: math-fun(a)mailman.xmission.com, William Ackerman <wba(a)alum.mit.edu> > >This reminds me of another famous swapping hack, often used by bit-bumming assembly >language hackers (such as myself). You want to swap two things--memory, register, >whatever, and you have XOR instructions. You need to have XOR instructions that go both >ways: if swapping a register with memory, you need instructions that can XOR a register >out to memory. The 360, and Intel, being monstrously CISC machines, have them. I used >this hack many times in my youth. > >A -->XOR--> B // That is, set B = A^B >B -->XOR--> A >A -->XOR--> B > >The 360 had "block XOR" instructions ("XORM"? Can't be bothered to look it up.) You >could XOR one long block of memory onto another. So you could use this hack to swap two >blocks of memory, without any temporaries.

1 0

Re: [math-fun] History of swap/exch computer instructions ?
by Bill Gosper 14 Mar '18

14 Mar '18

On 2018-03-13 17:21, Henry Baker wrote: > Thanks, Rich! > > I looked at the 7094 instruction set manual online, but didn't see > anything like an exchange/swap instruction. > > I looked at an online GE645 instruction set manual, but didn't find > anything there. > > Exchange/swap were considered back then for two reasons: > > 1. memory & registers were extremely expensive, so a single > instruction exchange/swap would save both data/register memory and > instruction memory. > > 2. main memory was made from ferrite cores, so reading was > *destructive*. Since you had to write *something* back to memory > anyway, you might as well write something *else* just as easily as > writing back what you just read. > > (The PDP-8 curiously did this backwards: its "DCA" (Deposit and Clear > Accumulator) stored the accumulator and set it to zero, but the "LDA" > (LoaD Accumulator) instruction did *not* clear the memory location > from which it was loaded! It would be interesting to know if there > were any computers who "utilized" this *destructive read* "feature" of > core memory.) > > I do recall that some computers back then had the ability to exchange > a memory location with the *program counter*! This enabled fast > Fortran I subroutining (no stack; no recursion; no service) and > "co-routining". Perhaps the PDP-6/10 did this sort of thing as well. Yes, JSP A,(A) . The PDP-6 had every imaginable subroutine instruction, jsp, jsr, jda, and, of course pushj, the latter as a sop to the Lisp community. Ironically, pushj turned out to be so fantastically useful that hardly anybody used the others. There was also UUO (unused opcode), which trapped to a uuo handler that could implement any kind of calling sequence you could dream up. It was sometimes possible to "outbum" pushj code using using jsp with an "implicit calling sequence". Instead of storing arguments after the jsp and then skipping over them upon return, you returned to the immediately subsequent instructions, which contrived to mention the arguments, which the subroutine fetched via (possibly multilevel) indirect addressing, with indexing at every level. Given the 16 triple purpose accumulators, it was usually possible to rearrange your steps to suit the expectations of the subroutine. And, of course, you could transmit multiple arguments in the accumulators. It was the greatest order code ever devised. --rwg Also, I think HAKMEM mentions representing free storage as a linked list of exch instructions. (Talk about data execution.) At the time, the machine was ridiculed for devoting an entire halfword (18 bits) to address memory, since nobody could need nor afford an entire megabyte. Instead of "Just you wait!", DEC mumbled meekly about symmetry. > > At 03:59 PM 3/13/2018, rcs(a)xmission.com wrote: >>The PDP6 had EXCH A,M which swapped an Accumulator with a Memory location. >>The manual is dated 1964. >> >>At that time, EXCH as an atomic instruction was believed useful for certain >>safely-interruptible algorithms --- futzing with linked lists &c. >> >>Maybe check out an old IBM 7094 manual? >> >>Rich >>---- >>Quoting Michael Greenwald <mbgreen(a)seas.upenn.edu>: >>>On 2018-03-08 08:10, Henry Baker wrote: >>>>I'm curious as to the origin of the exch/swap instruction in computer >>>>instruction sets. >>>> >>>>Does anyone know the first computer having such an instruction? >>>> >>>>I'm not interested in the modern "compare-and-swap" type of >>>>instruction, which seems to have originated with Maurice Herlihy, but >>>>the original, non-conditional type. >>> >>>I don't think Maurice originated the instruction; I am pretty sure >>>some versions of it predated him by decades (IBM 370). He was just >>>the one who pointed out and proved that it was universal (in the >>>context of non-blocking synchronization), as was the pair LL SC. >>> >>>But I have no answer to your main question, sorry. >>> >>>>Yes, early computer scientists (before they were called that!) loved >>>>these instructions because they allowed for clever algorithms like a >>>>stackless GC algorithm. > >

3 2

Re: [math-fun] History of swap/exch computer instructions ?
by Henry Baker 14 Mar '18

14 Mar '18

Hi Allan: Remember LispM "locatives" ? LispM locatives enabled one to take the *address* of a location -- sort of akin to C's "&" (address-of) operation. (rotatef <A> <B> <C>) <=> (rotate &<A> &<b> &<c>) i.e., if we can reduce each expression to a locative, then we can pass it as a more-or-less normal parameter to a function call. At 08:50 AM 3/14/2018, Allan Wechsler wrote: >Henry's understanding of the macro/function distinction in CL differs from >mine. Even on the Lisp Machine, ROTATEF and SETF were both macros, though >the compiler knew about them and had specific optimization along the lines >Henry hints at. (I confirm that the rotation has leftward sense.) > >"Function" means specifically that arguments are evaluated in left-to-right >order, and that only the values of the arguments were passed; the internals >of a function have no access to the structure of the operand forms (as they >need to for ROTATEF and SETF). > >On Wed, Mar 14, 2018 at 10:27 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> One other point about EXCH/SWAP instructions: >> >> Over the past decades I've played with these kinds of instructions >> via Common Lisp's "ROTATEF" function: >> >> (rotatef (aref array i) (aref array j) (aref array k)) >> >> does a circular permutation (rotate left, I believe): >> >> array[i]<-array[j]<-array[k]<-array[i] >> >> Common Lisp places no requirement that these locations come from the >> same array; I merely did this to indicate that this was a "location" >> type of function akin to "SETF", rather than a "value" type of function. >> This made a lot more sense on the Lisp Machine, where rotatef could be >> an actual *function*, rather than just a very smart *macro*. >> >> Of course, Common Lisp's rotatef can take any number of arguments; 0,1 >> are no-ops; 2 is SWAP/EXCH. >> >> I have found the 3-argument version of rotatef perhaps the most useful >> for playing around with linked lists. I'm curious why this was never >> noticed by Knuth & others. Perhaps I'm the only one in the Lisp >> community that has ever used this rotatef feature? >> >> At 11:15 PM 3/13/2018, Bill Gosper wrote: >> >Yes, JSP A,(A) . The PDP-6 had every imaginable subroutine instruction, >> >jsp, jsr, jda, and, of course pushj, the latter as a sop to the Lisp community. >> >Ironically, pushj turned out to be so fantastically useful that hardly anybody >> >used the others. >> >There was also UUO (unused opcode), which trapped to a uuo handler that >> >could implement any kind of calling sequence you could dream up. >> >It was sometimes possible to "outbum" pushj code using using jsp with >> >an "implicit calling sequence". Instead of storing arguments after the jsp >> >and then skipping over them upon return, you returned to the immediately >> >subsequent instructions, which contrived to mention the arguments, which >> >the subroutine fetched via (possibly multilevel) indirect addressing, with >> >indexing at every level. Given the 16 triple purpose accumulators, it >> >was usually possible to rearrange your steps to suit the expectations of >> >the subroutine. And, of course, you could transmit multiple arguments >> >in the accumulators. It was the greatest order code ever devised. >> >--rwg >> > >> >Also, I think HAKMEM mentions representing free storage as a linked list >> >of exch instructions. (Talk about data execution.) >> > >> >At the time, the machine was ridiculed for devoting an entire halfword >> >(18 bits) to address memory, since nobody could need nor afford an entire >> >megabyte. Instead of "Just you wait!", DEC mumbled meekly about symmetry.

1 0