pardo@june.cs.washington.edu (David Keppel) (10/27/88)
As a kid I read part of a book called "The Trachtenberg System of Math" or some such. The basic idea was that there were several rules that could be applied to *all* numbers to do *very* fast (linear in number of digits?) multiplies and multi-row adds. Unlike the books of the variety "how to do fast math in your head", this was not just a collection of tricks useful in certain situations (e.g., to multiply by 10, just add a zero to the end ...), rather it was a theory. I've since forgotten all the details. I'm sitting here reviewing hardware adders, multipliers, ... and wondering if anybody has ever tried to apply the Trachtenberg stuff to computers? Anybody? ;-D on ( Numbered? *My* days are alphabetical ) Pardo -- pardo@cs.washington.edu {rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo
aho@cory.Berkeley.EDU (Alex Ho) (10/27/88)
In article <6232@june.cs.washington.edu> pardo@cs.washington.edu (David Keppel) writes: >As a kid I read part of a book called "The Trachtenberg System of >Math" or some such. The basic idea was that there were several rules >that could be applied to *all* numbers to do *very* fast (linear in >number of digits?) multiplies and multi-row adds. this system sounds pretty interesting. do you have a reference to the original source, a book or a more recent magazine article, by any chance. thank you very much alex Alex Ho University of California, Berkeley aho@cory.berkeley.edu ...ucbvax!cory!aho
matloff@bizet.Berkeley.EDU (Norman Matloff) (10/27/88)
In article <6821@pasteur.Berkeley.EDU> aho@cory.Berkeley.EDU.UUCP (Alex Ho) writes: *In article <6232@june.cs.washington.edu> pardo@cs.washington.edu (David Keppel) writes: *>As a kid I read part of a book called "The Trachtenberg System of *>Math" or some such. The basic idea was that there were several rules *>that could be applied to *all* numbers to do *very* fast (linear in *>number of digits?) multiplies and multi-row adds. *this system sounds pretty interesting. *do you have a reference to the original source, *a book or a more recent magazine article, by any *chance. I think that the title is VERY close to what David remembers it as. However, as I recall, the system was NOT as far-reaching as David seems to be implying. It consisted of a bunch of specialized rules (e.g. similar to the well-known fact that a number is divisible by 3 iff the sum of its digits is divisible by 3) that did NOT apply to all situations. But maybe my memory is wrong on this. Interesting sidelight: Trachtenberg invented his system while in prison, I think a Nazi prison. He whiled away the hours by inventing all these speedy-arithmetic rules. Norm
rik@june.cs.washington.edu (Rik Littlefield) (10/27/88)
In article <6821@pasteur.Berkeley.EDU>, aho@cory.Berkeley.EDU (Alex Ho) writes: > In article <6232@june.cs.washington.edu> pardo@cs.washington.edu (David Keppel) writes: > >As a kid I read part of a book called "The Trachtenberg System of > >Math" or some such. The basic idea was that there were several rules > >that could be applied to *all* numbers to do *very* fast (linear in > >number of digits?) multiplies and multi-row adds. > > this system sounds pretty interesting. > do you have a reference to the original source, > a book or a more recent magazine article, by any > chance. > I believe you are looking for "The Trachtenberg Speed System of Basic Mathematics", (translated and adapted) by Ann Cutler and Rudolph McShane, copyright 1960, published by Doubleday and Company, Garden City, NY, Library of Congress 60-13513. Be prepared for disillusionment -- I believe the content is not as suggested above. In fact, the Trachtenberg system for multiplication by arbitrary numbers is still an O(MN) process for M- and N-digit numbers. Trachtenberg just computes the partial products for each pair of digits in such an order that the partial sum-of-products remains a small number that you can usually keep in your head. This lets you write down the product directly, right-to-left, without going through the usual bother of writing down all the partial products. Cute, but it's hard to see how it applies to hardware multipliers. --Rik Disclaimer: I got my copy as a gift probably 15 years ago, decided at the time that it wasn't worth my while, and never did read it all the way through. The interpretation above is based on a 3-minute scan of one chapter.
gert@prls.UUCP (Gert Slavenburg) (10/27/88)
The Trachtenberg system may not do what you are looking for, however, there is a technique which is interesting, and has some of the desired properties. The technique I am referring to is called 'Residue Arithmetic' or 'Chinese Remaindering'. It is a technique which allows you to do integer addition, subtraction and multiplication as concurrent operations (independent on each 'digit', without inter 'digit' carry). Note the quoted use of 'digit'.... The catch is that conversion from/to other codes is *very* computationally intensive, that digit arithmetic requires table lookup, and that magnitude comparison, sign test and division are prohibitively expensive. However, the arithmetic system can (and has been) used in signal processing systems that only require multiplication, addition and subtraction and that have many more internal computations than input/output conversions. For those interested, a pointer to a list of pointers : F.J. Taylor, 'Residue Arithmetic : A tutorial with examples', IEEE Computer, May 1984, pp. 50..62. Let's see some postings of architects that have built actual hardware based on this method ! By the way, this number system was first described in a 3'rd century Chines book. They must have been doing advanced research in signal processing :-) :-). Disclaimer : I am *not* a specialist on this topic. I just looked at it once as a potential method for doing additive music synthesis (where you only have real-time computations and output, no input). Don't ask me to explain how it works - just read the article yourself.
dick@ccb.ucsf.edu (Dick Karpinski) (10/28/88)
In article <6821@pasteur.Berkeley.EDU> aho@cory.Berkeley.EDU.UUCP (Alex Ho) writes: >In article <6232@june.cs.washington.edu> pardo@cs.washington.edu (David Keppel) writes: >>As a kid I read part of a book called "The Trachtenberg System of >>Math" or some such. The basic idea was that there were several rules >>that could be applied to *all* numbers to do *very* fast (linear in >>number of digits?) multiplies and multi-row adds. > >do you have a reference to the original source, I just checked for Trachtenberg in Univ of Calif Melvyl system and found a book (at UCSD) called Trachtenberg Speed Math by Ann Cutler in 1975 through Doubleday. The originator was one Jakow T. who seems to have been born in 1888. Dick Dick Karpinski Manager of Minicomputer Services, UCSF Computer Center UUCP: ...!ucbvax!ucsfcgl!cca.ucsf!dick (415) 476-4529 (11-7) BITNET: dick@ucsfcca or dick@ucsfvm Compuserve: 70215,1277 USPS: U-76 UCSF, San Francisco, CA 94143-0704 Telemail: RKarpinski Domain: dick@cca.ucsf.edu Home (415) 658-6803 Ans 658-3797
daryl@ihlpe.ATT.COM (Daryl Monge) (10/31/88)
I still have the book from Junior High. The book information is: The Trachtenberg Speed System of Basic Mathematics Translated and adapted by Ann Cutler and Rudolph McShane Published by Double Day in 1960. My paperback version was printed in 1967. The book has seven chapters on multiplication, addition, division, and square roots. The seventh chapter contains an algebraic description of the method. Daryl Monge UUCP: ...!att!ihcae!daryl AT&T CIS: 72717,65 Bell Labs, Naperville, Ill AT&T 312-979-3603
steve@obed.uucp (stephen Samuel) (11/03/88)
In article <6821@pasteur.Berkeley.EDU>, aho@cory.Berkeley.EDU (Alex Ho) writes: > In article <6232@june.cs.washington.edu> pardo@cs.washington.edu (David Keppel) writes: > >As a kid I read part of a book called "The Trachtenberg System of > >Math" or some such. > > this system sounds pretty interesting. Do you have a reference > to the original source, a book or a more recent magazine article, > by any chance. > ...ucbvax!cory!aho I found it in the Edmonton Public Library under 'calculators' (This was before I got into 'real' computers. I was looking for neat things to do with my TI-58. As someone else pointed out, the book isn't really all that general purpose. It gives some nice short-cuts and stuff and is (to some extent) dependant on some of the odities of base-10 math. Pieces might, however, be very applicable to computers, since he was trying to do as much as possible without having to do any more than add, subtract, and multiply/divide by 2. -- Stephen samuel !alberta!{obed,edm}!steve Look on the bright side... It might have worked!