March 2018 - mathfun@mailman.xmission.com

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

14 Mar '18

Re: (rotatef a b c) <=> (progn (rotatef a b) (rotatef b c)) Not so fast! For example, (rotatef result freelist (cdr freelist)) has the effect of: (setq result (cons nil result)) or (push nil result) Try your suggestion: (setq freelist (list nil nil nil nil)) (NIL NIL NIL NIL) > (setq result 'end) END > (rotatef result freelist (cdr freelist)) NIL > result (NIL . END) > freelist (NIL NIL NIL) > (setq freelist (list nil nil nil nil)) (NIL NIL NIL NIL) > (setq result 'end) END > (rotatef result freelist) NIL > (rotatef freelist (cdr freelist)) encountered a Lisp error: Error in CDR [or a callee]: END is not of type LIST. Automatically continuing. To reenable the Lisp debugger set *debugger-hook* to nil. Oops! At 09:05 AM 3/14/2018, 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 > >> Sent: Wednesday, March 14, 2018 at 3:50 PM >> From: "Allan Wechsler" <acwacw(a)gmail.com> >> To: math-fun <math-fun(a)mailman.xmission.com> >> Subject: Re: [math-fun] History of swap/exch computer instructions ? >> >> 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

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

14 Mar '18

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.

3 2

[math-fun] a nice day
by françois mendzina essomba2 14 Mar '18

14 Mar '18

Nice day in Yaoundé today... log(2)=sum((-1)^k*(1-1/2^k)*zeta(k), k= 2..infinity); An improvement in convergence. S(n) = sum((-1)^k*(1-1/2^k)*zeta(k), k= 2..n); log(2) = (S(n+1) + S(n))/2 ; n ----- infinity... FME...

2 1

[math-fun] Piday
by françois mendzina essomba2 14 Mar '18

14 Mar '18

In memory of Pi... a(n+1)=2^(n+3/2)*sqrt(1/r-((1-2^(-2*n-1)*(a(n))^2*r)^(1/r)+1)^(r/2)/(r*2^(r/2))); a1=2^(3/2)/sqrt(r) ; r in R ; n----infinity ; a(n) ---- Pi.

1 0

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

13 Mar '18

[The list software objected to this message; I don't know why. Retrying. -- Rich] Date: Tue, 13 Mar 2018 21:13:52 -0400 Subject: Re: [math-fun] History of swap/exch computer instructions ? From: wba <wbackerman(a)gmail.com> I the early days, many computers used the read-clear and write-to-previously-cleared properties of core memory. To recapitulate how that worked, a memory cycle began by sending a pulse to the core that clears it, while sense amplifiers sense the weak signal telling whether or not the core "turned over". Then the new data was written back by selectively sending pulses to the core in the other direction, setting bits to 1. Even if you only wanted to read, or only wanted to write, you had to do both halves of the cycle, to rewrite what you read, or to pre-clear what you were about to write. These properties were used for "add to memory" types of instructions, as well as various atomic synchronization primitives, such as semaphores. And, of course, for reg<->mem swaps. The atomic synchronization primitives were harder to implement when core memory got replaced by plain RAM. The DEC PDP-1 at the Research Laboratory of Electronics at MIT (a number of correspondents on this list remember that machine) had an interesting application of swapping something with memory. The time-sharing system needed to swap whole memory fields (4096 words!) onto and off of the drum when switching processes. A given field on the drum (one revolution, 4096 bits, 18 fixed tracks) had to be read into core, while the previous contents of core were written to a different 18 tracks. This required a sort of "supraluminal" information transfer. Faster than light? No. Just faster than the drum's rotation. Writing bits onto a track required blasting a powerful pulse from the write amplifiers onto the write heads. The electrical noise from this blast completely overwhelmed the sensitive read amplifiers trying to listen to another track. So they took advantage of the fact that whatever pulse was delivered to the write heads would have its magnetic field sort of smeared out in space, because the heads rode about .001 inches above the surface. Similarly, the read heads would "hear" an average of the smeared out magnetic field of the drum bit going by. So the mechanism would read data from memory, clearing same and holding that memory word open, and then blast that onto the desired write track. Just before the blast occurred, the read heads on the other track could sort of hear the other bit coming. The read amplifiers sensed the yet-to-arrive data just before the blast, and write that back into core.

1 0

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

13 Mar '18

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. 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.

1 0

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

13 Mar '18

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. 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

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

13 Mar '18

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 2

[math-fun] Common subsequence length
by David Wilson 11 Mar '18

11 Mar '18

Let S be a finite set with |S| = s. Let A be a finite random sequence of elements from S with |A| = a. Let B be a finite random sequence of elements from S with |B| = b. What is the expected length f(s, a, b) of a longest common subsequence of A and B? As an example, let A and B be finite sequences of 10 decimal digits with |A| = |B| = 10. Then S = set of decimal digits with |S| = 10. Two possible values of A and B are A = (3,1,4,1,5,9,2,6,5,3) B = (1,4,1,4,2,1,3,5,6,2) A longest common subsequence of A and B is (1,4,1,2,5) of length 5.

3 4

[math-fun] Just two more to go ...
by Hilarie Orman 11 Mar '18

11 Mar '18

Another global disaster looms as we approach Vonnegut crystalization boundary: http://science.sciencemag.org/content/359/6380/1136 Hilarie

3 2