Conference rusure::math

    The VAX/VMS Run-Time Library includes the routine STR$DIVIDE.  It'll
    take a little time to get the 'exponent' parameters set up right, but
    it'll do what you want.

    The multi precision package MP can do that (and a lot more...)
    It's written in portable FORTRAN.  I have a copy somewhere.

    The EMUL/EDIV instructions in assembler can also be used to write
    simple multi precision routines.

    - Jim

    
    Remember the way you used to do long division
    
    
                    ____4________
    		23  )  9999999999
                       92
    		       --
    			79
    			69
    			--
    			109...
    
    
    Well, just do that, but instead of using strings, or base ten, do
    it base 2**15!  That gives you room to do "single digit" multiplies
    etc. without overflowing a VAX longword.
                 
    
    
    /Bevin
    
    PS: While you're at in, consider the foresight of a company that
    produces an RTL with LIB$ADDX, LIB$SUBX, but no multiply or divide...
    

    Is STR$DIVIDE considered too easy?  Or not playing the game?
    
    How about OTS$DIV_PK_LONG? or OTS$DIV_PK_SHORT? or the VAX instruction
    DIVP?
    
    If I had to do it in an environment without these or similar aids,
    I guess I'd automate what we learned in grade school.  Separate
    out a block of leading digits from the dividend which is greater
    than the divisor but less than 10* divisor.  Estimate a quotient
    from the first n digits of block and divisor, and correct if necessary
    by multiplication and subtraction.  Store one digit of the quotient,
    concatenate the remainder and the rest of the dividend, and repeat
    the process.

    Everybody types faster than I do, especially when the phone rings.

    Also see Section 4 "Arithmetic" in volume 2 (Seminumerical Algorithms)
    in Knuth, the section entitled "The Classical Algorithms" (in the
    first edition this is section 4.3.1.  The discussion on division
    goes from page 235 through 240, with "Algorithm/Program D" providing
    the "answer".  The second edition of this volume has, in general,
    much more material and has been extensively rewritten, so I would
    advise finding the equivalent there -- but I don't have a copy on
    hand.)
    
    				Topher

    Thanks for all the answers. I'll try to get the books mentioned.
    
    As for the STR$DIVIDE, of course I thought about it but if the number
    is larger the 65535 digits, it won't work, right ?
    
    I also take a look at IXP.
    
    I was actually more intersted in the algorithm, not solutions,
    but I guess I take a look at those books.
    
    Can I have a source listing of MP or IXP ?

     	Julian.
    

$!	Division of any length integer by a short integer.
$!
$!	Author:   Eric Osman 8/28/87
$!
$!	Usage:
$!
$!		@div n m flag
$!
$!	If flag is 1, quotient and remainder are printed out and left in global
$!	variables "answer" and "remainder".
$!
$!	If flag is omitted, routine silently sets up "answer" and "remainder"
$!	but doesn't print anything.
$!
$!	Serving suggestion:
$!
$!		$ @div n m
$!		$ @mul 'answer' ...     ! use previous answer in new calculation
$!
$ on warning then @tt:
$ dd = p1
$ divisor = f$integer (p2)
$ interactive_flag = p3
$ if interactive_flag .eqs. "" then interactive_flag = "no"
$ remainder == 0
$ answer == ""
$ lup:
$ next_answer_digit = remainder / divisor
$ gosub append
$ remainder == remainder - next_answer_digit * divisor
$ gosub bring_down
$ goto lup
$ append:
$ answer == answer + f$string (next_answer_digit)
$ return
$ bring_down:
$ if dd .nes. "" then goto more_left
$ remove_zeroes:
$ if f$extract (0,1,answer) .nes. "0" then goto no_more_zeroes
$ answer == "xxxxx0"+answer-"x0"-"x0"-"x0"-"x0"-"x0"-"x"-"x"-"x"-"x"-"x"
$ goto remove_zeroes
$ no_more_zeroes:
$ if answer .eqs. "" then answer == "0"
$ if interactive_flag then -
    write sys$output f$fao ("!AS r. !ZL", answer, remainder)
$ exit
$ more_left:
$ bring_down_digit = f$extract (0,1,dd)
$ dd = dd - bring_down_digit
$ remainder == remainder * 10 + f$integer (bring_down_digit)
$ return

$!	Multiplication of any length integer by a short integer.
$!
$!	Author:   Eric Osman 8/28/87
$!
$!	Usage:
$!
$!		@mul n m flag
$!
$!	If flag is 1, product of n and m is printed out and left in global
$!	variable "answer".
$!
$!	If flag is omitted, routine silently leaves answer in "answer" but
$!	doesn't print it out.
$!
$ short = p1
$ long = p2
$ interactive_flag = p3
$ if interactive_flag .eqs. "" then interactive_flag = "no"
$ if f$length(short) .le. f$length(long) then goto ok
$ temp = short
$ short = long
$ long = temp
$ ok:
$ if f$length (short) .le. 3 then goto ok_size
$ write sys$output "Sorry, one of the numbers must be small!"
$ exit
$ ok_size:
$ short = f$integer (short)
$ chunk_size = 6
$ zeroes = 6-f$length(long)+f$length(long)/chunk_size*chunk_size
$ long = f$fao ("!''zeroes'*0") + long
$ answer == ""
$ long_pos = f$length(long) - chunk_size
$ carry = 0
$ fill = f$integer ("1" + f$fao("!''chunk_size'*0"))
$ more:
$ if long_pos .lt. 0 then goto all_done
$ more_product = -
  f$string(carry+short*f$integer(f$extract(long_pos,chunk_size,long)))
$ if f$length (more_product) .lt. chunk_size then more_product = -
    f$fao ("!''chunk_size'ZL", f$integer (more_product))
$ carry = -
    f$integer (f$extract (0, f$length (more_product) -chunk_size,more_product))
$ more_product = f$extract (f$length (more_product) - chunk_size, chunk_size, -
    more_product)
$ answer == more_product + answer
$ long_pos = long_pos - chunk_size
$ goto more
$ all_done:
$ answer == f$string(carry) + answer
$ remove_zeroes:
$ if f$extract (0,1,answer) .nes. "0" then goto no_more_zeroes
$ answer == "xxxxx0"+answer-"x0"-"x0"-"x0"-"x0"-"x0"-"x"-"x"-"x"-"x"-"x"
$ goto remove_zeroes
$ no_more_zeroes:
$ if answer .eqs. "" then answer == "0"
$ if interactive_flag then write sys$output answer

    Re 9,10:
    
    Eric, 
    
    	these procedures are nice but they don't help if you have two
    long integers to divide. That was/is the algorithm I am looking
    for. 
    
     o Any length integer by short integer - I know
     o Short integer by short integer      - I know
     o Any length by any length            - ?
    
    
	Julian.
    
    

    Here's how I do it :-)
    
Lisp> (truncate 43242353534153415616431543545231534 43215345435345345435)
1000624965473166 ;
37439361143052134324
Lisp> 
    
    The first value is the quotient, the second is the remainder.
    
    Dan

>	Thanks, Eric, but
>	long divided by short I know, but won't help me do
>	long divided by long


I think it can help you.  Think about how we do regular long
division on paper.  FOr instance:

                   ______________________
	333444555  )217745267623562532634

We don't really do long divided by long.  We divide the 3
into the 21 and get 7, right ?  We don't put the 7 over the 1 of
21, we put it further to the right according to the length of
the divisor, which is 9 digits in our example.

The point is, we only really "do" short divided by short, and
the long divided by long only gets generated by our divide/multiply/
subtract/compare/bring down cycle.

Right ?

/Eric