Working with only local integers, global integer arrays, +, -, /, *, set var, re

Question

Working with only local integers, global integer arrays, +, -, /, *, set var, read var, loops, if statements and functions, how would one divide out extremely large numbers stored in arrays in any given base? I've been trying to figure this out, but the closest I could come to was getting a very rough guess of the quotient.


Right now, I have it set up in base 2^30 (word size of 2^30) with a maximum divisor of int(SquareRoot(2^30)) to prevent overflow in the calculations. I'm just doing long division atm ;|.


So, is there any way to divide this out digit by digit efficiently? I don't think polynomial division would work that well either as the numerators and denominators of the fractions would become very massive rather quickly and it would be extremely slow. These numbers might easily be 120^300 in size, so I really need to figure out a way to handle this.


Anyone have any ideas?

Pseudocode, so long as it uses the basics (FUNCTION, DECLARE, SET, etc) will help me understand the algorithm ^)^. Comments explaining why things are done will help as well.


I have addition and multiplication done, so you can freely call those. I'd rather not do subtraction as that would require me to compliment the numbers =|, but I do know how to write the subtraction algorithm, so if it's really necessary, you can just magically call that one too.


This is my current division algorithm

http://pastebin.com/iLfuntbk


In the above, toBeDivided is a digit within a linked list that represents a number. It is a linked list for fast deallocation of a number with a lot of digits (2 lines of code to destroy the whole thing).


Don't worry about allocation, deallocation, add, or remove. Just be sure to mention in the adding whether to add it after a digit or before a digit, or to the front or back =P. Also, don't worry about the +, -, or * functions.



So if anyone could figure out a way to divide two numbers stored in linked lists without, that would be awesome =). And please, no base conversion to binary for binary subtraction (needs to be fast >.<) and no shifting because the language this is being written in doesn't support shifting. The language pretty much has a few basic functions, +, -, *, /, the ability to declare functions and return values (not pointers), the ability to declare locals, the ability to take values (no pointers), loop blocks, and if statements. It also supports integers, floats, booleans, and strings =.


And to give you a better idea. The number 123456 stored in a linked list just using a word size of 10

[0,true]<->[1,false]<->[2,false]<->[3,false]<->[4,false]<->[5,false]<->[6,false]<->[0,true]

The second value in the boxes refers to the head marker, which is just a boolean =).

Explanation / Answer

First note that for any integers a, b, q, r, the relation a = bq + r is equivalent both to a = -b×-q + r and to -1 - a = b(-1 - q) + b - 1 - r, so that the pair (q,r) is a solution for the division of a by b if and only if (-q,r) is a solution for the division of a by -b, and also if and only if (-1 - q,b - 1 - r) is a solution for the division of -1 - a by b. It will therefore suffice to prove existence and uniqueness of these solutions assuming b > 0 and a = 0: existence and uniqueness in the other cases will follow from it by these equivalences. We assume these inequalities henceforth, and observe that they imply that q = 0 for any possible solution (as q = -1 together with the required r 0 For fixed divisor b one proceeds by induction on the size of the dividend a. All cases with a 0 and r = 0 since a