Alogrithims Needed
Author Message
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
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
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
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
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
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
Alogrithims Needed
Okay. Here's my attempt. I intend to write the code in Modula-2, but

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:=input-divisor;
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
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
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
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

 Page 1 of 1 [ 13 post ]

Relevant Pages