View Full Version : Division algorithm needed
Algorithm
07-17-2002, 07:16 AM
Does anyone know of a good division algorithm that works without resorting to multiplication tables or extensive trial-and-error? I'm in the process of creating a script that can handle billion-digit numbers without rounding, and it's somewhat impractical to employ tables when you're working with base-10,000,000 numbers.
Any help is appreciated.
jalarie
07-17-2002, 04:26 PM
A billion digits?! :eek: The following will take a while, but it should get the job done:
<!doctype HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/REC-html40/loose.dtd">
<html lang="en-US">
<head>
<title>Divide</title>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-5">
<meta name="Author" content="James A. Alarie - jalarie@umich.edu" />
<link rev="made" href="mailto:jalarie@umich.edu" />
<meta name="MSSmartTagsPreventParsing" content="TRUE" />
<script type="text/javascript">
<!-- Hide this code from non-JavaScript browsers
function DivideIt() {
f1=document.forms[0]; // abbreviation
Dividend=f1.Dividend.value;
Divisor =f1.Divisor.value;
Quotient='';
D1=Dividend.split('');
D2=0;
for (ix1=0; ix1<Dividend.length; ix1++) {
D2=D2*10+D1[ix1]*1;
Quotient=''+Quotient+Math.floor(D2/Divisor);
D2=D2%Divisor;
}
f1.Quotient.value=Quotient;
}
// End hiding -->
</script>
</head>
<body bgcolor="#ffffee" text="black"
link="blue" vlink="#800088" alink="red">
<!-- Page Header -->
<center><h1>Divide</h1></center>
<hr />
<!-- Content -->
<center>
<form action="">
Dividend:
<input type="text" name="Dividend" onfocus="this.select();" />
/
Divisor:
<input type="text" name="Divisor" onfocus="this.select();" />
=
Quotient:
<input type="text" name="Quotient" onfocus="this.select();" />
<br /><br />
<input type="button" value=" Divide " onclick="DivideIt();" />
<input type="reset" />
</form>
</center>
<!-- Page Footer -->
<br clear="all" /><hr />
Written on July 17, 2002, by:
<a href="mailto:jalarie@umich.edu">James Alarie</a>
</body>
</html>
:D
Algorithm
07-17-2002, 10:07 PM
No, no, that won't work. Javascript rounds numbers once they start getting above a quadrillion. Your method would introduce an unacceptable amount of error.
Perhaps the code I'm using would help: http://www.undefined.net/null/bignum.js
(Caution: This code is still quite buggy.)
What I need is a method that will divide the numbers a few digits at a time. Somewhat like long division, except all the long division methods I've encountered involve multiplication tables.
poccil
07-17-2002, 10:29 PM
Somehow, a query like this is not realistically possible in JavaScript, due in part to different implementations of JavaScript in different browsers, and also due to the fact that such a query does not seem to conform with the intended purpose of JavaScript.
A problem like this is better solved in C or another lower-end language.
Resident moderator Alex Vincent has plans (maybe even code?) for doing such things:
http://jslab.org/xns/
jalarie
07-18-2002, 04:29 PM
The above code DOES work and has nothing to do with JavaScript limitations as long as the dividend and quotient strings are less than the limit (30K?) of the language. It does it by doing the long division exactly as you were taught in school, one digit at a time.
:thumbsup:
Algorithm
07-18-2002, 10:57 PM
That's not the problem at all; your code works commendably well with small divisors. However, once the divisors get into the dozens-of-digits range, Javascript just rounds the poop out of it. I need code that can handle values of extreme size on either end of the equation.
jalarie
07-19-2002, 01:47 PM
:( Ah, right you are, Algorithm! I handled extreme-sized dividend and quotient, but forgot about the divisor. I'll try again as soon as I get a chance.
By the way, what is it you're trying to do? If you're trying to factor huge numbers, posibly to crack someone's public-key encryption, JavaScript is NOT the language to use. Neither is any other interpretive language; they're too slow.
Algorithm
07-20-2002, 08:19 AM
The divisor's the tough bit. I wish you luck.
Oddly enough, I started on this module so I could compress files created with one of my online applications (which uses Javascript only). My initial idea was to view the string as a number in base-26, and convert it to one in base-92. Needless to say, such a number would be extremely large. And although I have since abandoned this idea in favor of a more sane one, I still feel that such a module may be beneficial to those in the scripting community.
And, if on some distant day I need a script that can caculate the sum total of nosehairs in the population of China, I'll have it within reach. :D
Algorithm
07-22-2002, 02:03 AM
Does anyone know where I can get something like this?
Alex Vincent
07-25-2002, 03:07 AM
I do have code for this at the site Jason mentioned. Unfortunately, you may need a Mozilla 1.0 or later build to view the BigDecimal() documentation, which is what you're looking for.
Specifically,
http://jslab.org/xns/docs/BigD_divide.xml
http://jslab.org/xns/docs/BigDecimal.xml
vBulletin® v3.8.2, Copyright ©2000-2012, Jelsoft Enterprises Ltd.