Solved

# Div Procedure

Posted on 1998-11-21
Medium Priority
254 Views
I need Procedure/Function that can divide a string input with string too..
example the procedure name is divide

divide('9999999999999999','9999999999999999',output,comma);
writeln(output+'.'+comma);

output
======
1.0

can anyone help me? the input must be in string and the output must be in string too!

Thank You
0
Question by:ichen
• 5
• 5
• 2
• +5

LVL 3

Expert Comment

ID: 1216146
Function Divide(a,b: string): string;
Var
a1,b1: single;
Q: string;
i: integer;
Begin
Val(a,a1,i); Val(b,b1,i);
{ If you need check for error during Val() conversion,
you should see value returned at I variable }

Str(a1/b1, Q); Divide:=Q;
end;

If you really need integer and fractional parts of quotient to be separated, this can be easily corrected.
0

LVL 5

Expert Comment

ID: 1216147
What if a and b had 255 characters?  Using a single wouldn't work.  It is probably better to break it up into chunks of integers.
0

LVL 3

Expert Comment

ID: 1216148
You're right; an 'extended' variable allows a number + o - 10^5000. Of course, precision won't be so good with those monster numbers...
0

LVL 5

Expert Comment

ID: 1216149
I think single is accurate to 7 places, but I am not sure...

What I would do is divide using a number system of base 10000.  Take every chunk of four digits and place them into a digit of base 10000 (stored in an integer variable).  Then divide the numbers.  Take the quotient and convert it from the base 10000 integer digits to a string a numbers.
0

LVL 4

Expert Comment

ID: 1216150
Don't yuo understand, that ichen needs strings only to not operating with numbers, because he needs such calculations, as i.e. 2^1000. None of Pascal types can do this
(extended too)!
0

LVL 1

Author Comment

ID: 1216151
I don't want the exponent (^)...

0

LVL 5

Expert Comment

ID: 1216152
jack_p50:  I understand that strings are needed.  But you have to convert them to a numeric type to perform calculations on them.

After looking into more deeply, I think you should take groups of two base 10 digits instead of four.  Use a number system of base 100, and store each base 100 digit in an integer.  Therefore there is no chance for overflow (100*100 = 10000 < 32767).  The maximum number of base 10 digits would be the maximum size of a string (255).  If you wanted to go further, you could use an array of characters rather than the standard string type.

Addition, subtraction, and multiplication operations can be implemented quite easily using this system.  Division is much more tricky!
0

LVL 3

Expert Comment

ID: 1216153
Dog: division can be achieved by performing a sequence of subtraction (as thos old machines, with a rotating handle, did).

Jack: ¿why do you say Pascal can't deal with a number such as 2^1000?

I really thought what Ichen needed was "string arithmetic", but he was not very explicit... :(

0

LVL 5

Expert Comment

ID: 1216154
Vikiing:  I know that...but what if you are dividing 87598749599357283459823457293847592349752834588484373873858438383 by 5535242443245254553525434?  How many subtractions are you going to need to do?  Trillions!!  Like I said, it is pretty tricky.
0

LVL 2

Expert Comment

ID: 1216155
I think it is time for ichen to specify what (s)he wants - either a simple solution that would work, let's say, with integers less than 32767; or, if a solution that can precisely divide extremely large numbers (255 digits or more) is needed.

BTW, some time ago I was playing with string division, I could do 255-digit numbers, but it was rather slow (about one division per second of two 60-digit numbers on a 486sx/40 - which was enough for me then). However, with some advanced optimizations, we could get significantly more than that.

0

LVL 5

Expert Comment

ID: 1216156
The procedure to string divide a 1000-digit number would be not much different than the procedure to divide a 255-digit or even a five-digit number.  A procedure can be written to divide x digits into x or x+1 digits;  after this task is taken care of, the number can be broken down using recursion and subtraction.
0

LVL 3

Expert Comment

ID: 1216157
Dear Dog:
The mechanism to achieve a division by a sequence of subtractions is quite different from what you think. Of course, it can be done the way you suggest (after all, the same way a product is a sequences of addings, division is a sequence of subtractions); but actual process (keeping the same essence) is a bit more tricky.

Let's have the division you suggested:
87598749599357283459823457293847592349752834588484373873858438383to be divided by 5535242443245254553525434

These are the steps:
1) Align both numbers AT LEFT
a) 8759874959935728345982345...
b) 5535242443245254553525434

2) Start subtracting b) from a); you can do it just once, because at second time, result is negative. Now you have the first digit of result: number 1

3) After subtraction, first part of a) became 32246325166905... (+ o -)

4) Shift b) one place to right, thus you now have:
32246325166905...
5535242443245...
to subtract. That subtraction can be done 6 times (5 x 6 = 30 because 5 x 7 = 35 --> too much). That 6 becomes the second digit of result.

Process runs that way until result is got. The amount of subtractions, in the worst case, is approx. the difference in length of both operands multiplied by 9.

Your example can be solved in approximately (65 - 25) * 9 = 360 subtractions; a bit less what you thought, isn't it ?... :)

PS: this method was used with mechanical calculators, when electronic ones didn't exist yet, about first decades of century. Those tricky machines were totally MANUAL; they had 3 "registers", done with tiny numbered wheels, and a numeric keyboard:

1 #######      2 #######      <--- Numeric displays
3 #######

To divide 12345678 by 90123 user did this:
1) Type in 12345678. That value loads at "register" 3. With a special button, he shifts the value to lefmost point. That also moves a "pointer" at reg.2 to leftmost position.
2) A turn of crank will transfer 3 to 1, and counts "1" at reg.2
3) A button clears reg.3; another button clears reg.2
4) Type in 90123 (once again, it's loaded at reg.3). The same button shifts reg.3 at leftmost position (reg.2 pointer does the same).
5) Subtracting process begins. User start to crank BACKWARDS. Each turn of crank will count at reg.2, and leaves result of subtraction at reg.1 (reg.3 never varies). When subtraction can not longer be achieved, last turn of crank sounds a tiny bell. That indicates last turn mut be reversed (by cranking forward). In that moment, by pressing another button, reg.3 is right-shifted one place, and the same occurs with pointer at reg.2, and subtracting process starts again. When reg.3 reaches rightmost position, division is complete.

Those machines served to do 4 basic math.operations; I had a chance to see operators (at a foreign exchange office) using those machines, working at an **AMAZING** speed. Little jewels of human clever... :) :)

0

LVL 3

Expert Comment

ID: 1216158
My friend Joe: I've developed a math-string package (written in assembly language) for an ancient Digital's PDP-11/03 (in 1978). Although it's speed was a crap, it performed much faster than what you stated. I think your code could be enhanced a few...
0

LVL 2

Expert Comment

ID: 1216159
vikiing: OF COURSE it could be optimized... :) I just hacked the mentioned code together using pascal in about 10 minutes just to solve a math problem that my calculator won't handle. If I needed the speed, I would have used assembler, converted the string to binary-represented number and used one of the well-described-elsewhere dividing algorithms...... :)
0

LVL 27

Expert Comment

ID: 1216160
After looking a ichen's profile and that he has not answer for several days, I think that he must be playing computer games. However also from his profile I believe that his original question should be taken literally. So has anybody got a multi-precision arithmetic package? If so it is reasonably simple to convert the array's of binary digits into a string.
0

LVL 1

Author Comment

ID: 1216161
Thanks everyone. but i GOT the answer!!
Function Des2Hex32(Desimal: String; x: longint): String;
{Const      Konv = 9;}

Var R1, I, J,konv: Byte;
D1      : Word;
Code    : Integer;
Result,
T1, T2, T3, T4 : String;
{ T1 = Div
T2 = mod
T3 = byte }

Begin
Result:= ''; T2:= ''; D1:= 1;
T1:= Desimal; R1:= 0;
konv:= x;

While (D1 > 0) do
Begin
I:= 1; J:= 1;
Repeat
If (J = Length(T1)+1) then
Begin
Result:= B32[D1+1] + Result;
T1:= T2;
T2:= '';
If (Length(T1) = 0) and (Length(T2) = 0) then Break;
I:= 1; J:= 1;
End;

T3:= Copy(T1, I, J);
{ Dianggap desimal adalah string lalu diambil 1 persatu }
Val(T3, D1, Code);
{ Konversi ke numerik }
If (D1 div Konv = 0) then
Begin
Str(R1, T4);
If (Length(T2) <> 0) and (R1 = 0) or ((J > Length(T4)) and (R1 <> 0)) then
T2:= T2 + '0';
Inc(J);
End;
Until (D1 div Konv > 0);
Delete(T1, 1, J);

R1:= D1 mod Konv;
{ Dapatkan sisa pembagian }
Str(R1, T3);
{ Konversi ke string }
If (R1 <> 0) then
Insert(T3, T1, 1);
{ Tambahkan ke string desimal }

D1:= D1 div Konv;
{ Dapatkan hasil pembagian }
Str(D1, T3);
{ Konversi ke string }
Insert(T3, T2, Length(T2)+1);
{ Tambahkan ke string hasil }
End;

Writeln(Length(Result));
{  H:= H+length(result);}
Des2Hex32:= Result;
End;

0

LVL 10

Expert Comment

ID: 1216162
I can give you a code written in C. If this would help you send an email to rbr@physik.kfunigraz.ac.at
0

Accepted Solution

Artitis earned 400 total points
ID: 1216163
My english is not good, but I hope you will understand me.
You have said many good ideas, but here is the Function you wanted.
This Program is not optimized, but works, and fast enough.
May be, there are some bugs, but I hope there aren't.

const CipSk=100; { Max number of digits }
type strnum=string[CipSk];
var res,coma:strnum;

{kills first zerros}
procedure normalize(var sk:strnum);
var l:integer;
begin
l:=length(sk);
while (sk[1]='0') and (l>1) do
begin
dec(l);
sk:=copy(sk,2,l);
end;
end;

{from:=from-what}
function decsk(var from:strnum;what:strnum):boolean;
var sk,atmina,g1,g2:integer;
begin
g1:=length(from);
g2:=length(what);
atmina:=0;
while (g1>0) and (g2>0) do
begin
sk:=ord(from[g1])-ord(what[g2])-atmina;
if sk<0 then
begin
inc(sk,10);
atmina:=1;
end else atmina:=0;
from[g1]:=chr(sk+48);
dec(g1);
dec(g2);
end;
if (g1=0) and ((g2>0) or (atmina>0)) then decsk:=false
else
begin
while (g1>0) and (atmina>0) do
begin
sk:=ord(from[g1])-48-atmina;
if sk<0 then
begin
inc(sk,10);
atmina:=1;
end else atmina:=0;
from[g1]:=chr(sk+48);
dec(g1);
end;
decsk:=true;
normalize(from);
end;
end;

{ res . res_comma:=number1 / number2 }
function divide(number1,number2:strnum;var res,res_comma:strnum):boolean;
label beigt;
var active,rez:strnum;
cipskn1,cipskn2,cipskpalik,counter,lcomcip:integer;
iscomma,more1:boolean;
cip:char;
begin
normalize(number1);
normalize(number2);
rez:='';
if number2='0' then
begin
divide:=false;
res:='ERROR-DIVISION BY ZERRO';
res_comma:='';
exit;
end;
cipskn1:=length(number1);
cipskn2:=length(number2);
active:=copy(number1,1,cipskn2);
cipskpalik:=cipskn1-cipskn2;
iscomma:=false;
repeat
if active[1]='0' then active:='';
more1:=false;
while (length(active)<length(number2)) or ((length(active)=length(number2)) and (active<number2)) do
begin
if iscomma then cip:='0' else
begin
if cipskpalik<1 then
begin
iscomma:=true;
res:=rez;
rez:='';
if active[1]='0' then goto beigt;
cip:='0';
end else
begin
dec(cipskpalik);
cip:=number1[cipskn1-cipskpalik];
end;
end;
active:=active+cip;
if more1 then rez:=rez+'0';
more1:=true;
end;
counter:=0;
while (length(active)>length(number2)) or ((length(active)=length(number2)) and (active>=number2)) do
begin
decsk(active,number2);
inc(counter);
end;
if (rez<>'') or (counter>0) then rez:=rez+chr(counter+48);
until ((active[1]='0') and (cipskpalik<1)) or (length(rez)>=CipSk);
beigt:
if iscomma then res_comma:=rez else
begin
res:=rez;
res_comma:='0';
end;
if res='' then res:='0';
if res_comma='' then res_comma:='0';
divide:=true;
end;

begin
{ example }
divide('87598749599357283459823457293847592349752834588484373873858438383','5535242443245254553525434',res,coma);
writeln(res+'.'+coma);
end.

And the result is:
15825639165318846611553661548707938247866.9317545136404601734219539471638884189593471033066614411128142053196618368704407072579693232118576843

0

## Featured Post

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.