Author 
Message 
Dragisa Dur #1 / 13

Alogrithims Needed
: Does anyone have an algorithim or method for doing a divison of two : intger numbers a and b, such that only +, and * are used ? If I remember correctly, we had this in 2nd or 3rd year of elementary school. Try to consult some of your old elementary math books. In fact, read them thoroughly few times, you obviously need that badly. : Alex Farlie : Student at City University : LONDON dragisha

Sun, 01 Jul 2001 03:00:00 GMT 


Martin Tom Bro #2 / 13

Alogrithims Needed
On Wednesday, in article
Quote: > Does anyone have an algorithim or method for doing a divison of two > intger numbers a and b, such that only +, and * are used ?
There are several methods of varying efficiency. Are a & b variable precision numbers ? Quote: > I am also looking for help with the following. > Hash Tables > Binary Heaps or Priority Queues.
Try Donald Knuth's classic books for a reasonable introduction. Regards, 
Scientific Software Consultancy /^,,)__/

Sun, 01 Jul 2001 03:00:00 GMT 


Dragisa Dur #3 / 13

Alogrithims Needed
: > : > Does anyone have an algorithim or method for doing a divison of two : > intger numbers a and b, such that only +, and * are used ? : Division is repeated subtraction, so all you really need are : subtraction and comparison operations. I don't remember the exact : algorithm, but basically you want to repeatedly subtract the divisor : from the dividend until the dividend is 'used up'. This one is about algorith efficiency. You can do it in WHILE loop with one counter but it is most inefficient method. More efficient methods are very similar to elementary school method of integer division, but of course with base 2. Depending on language you use (ie. bitwise ops available) in it, you can implement it various ways. Original problem is probably targeted at this method, unless lecturer is clueless, but I can't believe she/he is. dd

Tue, 03 Jul 2001 03:00:00 GMT 


Dennis Nola #4 / 13

Alogrithims Needed
Quote:
>: > >: > Does anyone have an algorithim or method for doing a divison of two >: > intger numbers a and b, such that only +, and * are used ? >: Division is repeated subtraction, so all you really need are >: subtraction and comparison operations. I don't remember the exact >: algorithm, but basically you want to repeatedly subtract the divisor >: from the dividend until the dividend is 'used up'. > This one is about algorith efficiency. You can do it in WHILE loop with >one counter but it is most inefficient method. More efficient methods are >very similar to elementary school method of integer division, but of course >with base 2. Depending on language you use (ie. bitwise ops available) in >it, you can implement it various ways. > Original problem is probably targeted at this method, unless lecturer is >clueless, but I can't believe she/he is. > dd
Calculators have a lot to answer for. Fifty years ago, when I was in primary school we used to perform the division of two numbers using Multiplication, addition and subtraction as a matter of course. We used to call it "LONG DIVISION" That a current student would not know this I can understand, even if he had been taught it, being allowed to use a calculator would soon relagate that particular piece of knowledwe right down thers with responsibility and respect. What did surprise me is the replies that were posted. Regards to all, Dennis Dennis Nolan
"If a man is called to be a streetsweeper, he should sweep streets even as Michelangelo painted, or Beethoven composed music, or Shakespeare wrote poetry. He should sweep streets so well that all the hosts of heaven and earth will pause to say, here lived a great streetsweeper who did his job well." Martin Luther King, Jr.

Thu, 05 Jul 2001 03:00:00 GMT 


Peter Moyl #5 / 13

Alogrithims Needed
Quote:
>> >: > >> >: > Does anyone have an algorithim or method for doing a divison of two >> >: > intger numbers a and b, such that only +, and * are used ? >> Calculators have a lot to answer for. >I Agree with the point about calculators. >The purpose of the orignal question was todetermine if a formal set of rules >exisited for division. >so far the rules i have for operators are >0 is Zero >1 is Suc(Zero) >2 is Suc(Suc(Zero)) >.. etc >plus N,N> N >minus N,N > N >Multiply N,N> N >Where N is any natural number. >Rules: >plus (N,0) > N >plus (Suc(N),M)=Suc(Plus (n,m) >minus(N,0) > N >minus(suc(M),Suc(N))=minus(M,N) >Multiply(N,0)>0 >Multiply(N,Suc(M))> plus(N,Multiply(N,M) >I am trying to obtain a rule for divide N,N > N.(where N is anatural number).
A worthy endeavour. I'd like to suggest that the very first thing you do is to think in terms of "divide" producing a pair of natural numbers as the result. That is, the remainder is just as important as the quotient. It's been a while since I've looked at this sort of thing, but if I recall correctly division algorithms are usually based on the properties of multiplication more than on the "axiomatic" (so to speak) properties of division. That is, we tend to define division in terms of multiplication. The typical division algorithm works like this: given x and y, choose numbers a and b such that x = a*y + b; for example, you could choose a=0 and b=x; WHILE b >= y DO find a way to modify a and b such that (x=a*y+b) remains true and b gets smaller END (*WHILE*); (The obvious way to do this is just to subtract y from b each time around the loop, while incrementing a, but with a little extra thought you can find methods that will converge faster.) 
OS/2 help and software at http://eepjm.newcastle.edu.au/HTML/os2home.html

Sat, 07 Jul 2001 03:00:00 GMT 


Martin Harve #6 / 13

Alogrithims Needed
I think you'll find that in order to do long division the only multiplication required is of the base size, so it's normally best to just use shifts and subtracts. Nothing else needed for fixed precision numbers. MH. Quote:
> Calculators have a lot to answer for. > Fifty years ago, when I was in primary school we used to perform the division of two > numbers using Multiplication, addition and subtraction as a matter of course. > We used to call it "LONG DIVISION"
 Martin Harvey. Totally rewritten web pages at: http://www.harvey27.demon.co.uk/mch24/ "ALGOL 60 was a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors". C.A.R. Hoare BEGIN GEEK CODE BLOCK Version: 3.12
t 5 X R !tv b+ DI+ D+ G e++ h r z++> END GEEK CODE BLOCK You think my sig is long? Just you wait until I attach a uuencoded wav of Mahler II to it...

Tue, 10 Jul 2001 03:00:00 GMT 


Martin Harve #7 / 13

Alogrithims Needed
Okay. Here's my attempt. I intend to write the code in Modula2, but please forgive me if I inadvertently slip into Pascal. divide x by y to produce r remainder d. Considering positive integers only... I dare not go into two's complement arithmetic! so r*y+d=x after doing a couple of division examples, I found that division in binary is considerably easier than division in decimal. Decimal division example: 0246  5)1234 1000 = 5*200  234 200 = 5*40  34 30 =5*6  4 Binary division is absolutely trivial because you never have to multiply (ie take the divisor away more than once in any column), just shift the bits left and right! eg: 110100 ___________ 111) 101101101  11100000 = 10001101  1110000 = 11101  11100 = 1 Check: 110100 x 111 = 11100 + 1110000 + 11100000 = 101101100 remainder 1 So, the algorithm is now very simple. Well actually, there are some subtleties (eg a max of one subtraction ever needed per shift), and I haven't tested this, but you get the idea VAR input,divisor,result,remainder:CARDINAL; shift:INTEGER; BEGIN (*Shift the divisor so it's MSB is in the wordsize MSB*) shift:=0; result:=0; remainder:=0; WHILE divisor<=MAX(INTEGER) DO (*NB Integer one bit less than cardinal*) INC(shift); input:=input SHL 1; END; (* Okay. Now do the division *) WHILE shift>1 DO IF divisor<=input THEN input:=inputdivisor; result:=result+(1 SHL shift); END; divisor:=divisor SHR 1; DEC(shift) END; remainder:=input; END; Hope this helps. If someone would care to implement this and perhaps make a program that shows it working, then I'd be pleased :)  Martin Harvey. Totally rewritten web pages at: http://www.harvey27.demon.co.uk/mch24/ "ALGOL 60 was a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors". C.A.R. Hoare BEGIN GEEK CODE BLOCK Version: 3.12
t 5 X R !tv b+ DI+ D+ G e++ h r z++> END GEEK CODE BLOCK You think my sig is long? Just you wait until I attach a uuencoded wav of Mahler II to it...

Tue, 10 Jul 2001 03:00:00 GMT 


Martin Harve #8 / 13

Alogrithims Needed
Quote:
> If people put a complexity bound on thier divison > routine then some comparison could be drawn.
Well... if all other operations used are constant, then it's log(n) where n is the length of the divisor :) MH.  Martin Harvey. http://www.harvey27.demon.co.uk/mch24/ "ALGOL 60 was a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors". C.A.R. Hoare BEGIN GEEK CODE BLOCK Version: 3.12
t 5 X R !tv b+ DI+ D+ G e++ h r z++> END GEEK CODE BLOCK

Sun, 15 Jul 2001 03:00:00 GMT 


Martin Harve #9 / 13

Alogrithims Needed
Ooops... log(n), where n is the size of the divisor and log(n) is it's length in bits... all in big O notation of course :) MH. Quote:
> > If people put a complexity bound on thier divison > > routine then some comparison could be drawn. > Well... if all other operations used are constant, then it's log(n) > where n is the length of the divisor :) > MH. >  > Martin Harvey. > http://www.harvey27.demon.co.uk/mch24/ > "ALGOL 60 was a language so far ahead of its time that it > was not only an improvement on its predecessors but also > on nearly all its successors". C.A.R. Hoare > BEGIN GEEK CODE BLOCK > Version: 3.12
> t 5 X R !tv b+ DI+ D+ G e++ h r z++> > END GEEK CODE BLOCK
 Martin Harvey. http://www.harvey27.demon.co.uk/mch24/ "ALGOL 60 was a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors". C.A.R. Hoare BEGIN GEEK CODE BLOCK Version: 3.12
t 5 X R !tv b+ DI+ D+ G e++ h r z++> END GEEK CODE BLOCK

Mon, 16 Jul 2001 03:00:00 GMT 


Dennis Nola #10 / 13

Alogrithims Needed
Quote:
>Thanks. >The intial question of how rto divison without divde operator seem to have >sparked a good deal of response. If anybaody else has suggestions then by >all means post them. If people put a complexity bound on thier divison >routine then some comparison could be drawn. >Additonally in relation to the orignal question there are cases if you try >to define divison as set of recursive rules where it is not posible to get >a firm answer. Simmarly divison by zero is undefined. >However this thread seems to have deeveloped into a >" How to write a divide routine" thread.
I feel that any routine should be able to divide any arbitery length number by any other length number, the numbers can be of any sign too. Then testing of a set of various length divisors and dividends can be performed. Obviously to do division  Add, Subtract and Multiply must also be available for the same specifications, May I sugest the following TYPE NR; PROCEDURE NewNr( str : ARRAY OF CHAR): NR; PROCEDURE KillNr( nr : NR); PROCEDURE AddNrs( nr1, nr2 : NR): NR; PROCEDURE SubNrs( nr1, nr2 : NR): NR; PROCEDURE MultNrs( nr1, nr2 : NR): NR; PROCEDURE DivNrs( nr1, nr2 : NR): NR; PROCEDURE Nr2Str( nr : NR): PSZ; PROCEDURE WriteNr( f : File; nr : NR): LONGCARD; The last two can be used to either display the result or write it to a file; Regards Dennis Dennis Nolan
"If a man is called to be a streetsweeper, he should sweep streets even as Michelangelo painted, or Beethoven composed music, or Shakespeare wrote poetry. He should sweep streets so well that all the hosts of heaven and earth will pause to say, here lived a great streetsweeper who did his job well." Martin Luther King, Jr.

Tue, 17 Jul 2001 03:00:00 GMT 


