c++ - Integer division algorithm -

i thinking algorithm in division of large numbers: dividing remainder bigint c bigint d, know representation of c in base b, , d of form b^k-1. it's easiest show on example. let's try dividing c=21979182173 d=999.

• we write number sets of 3 digits: 21 979 182 173
• we take sums (modulo 999) of consecutive sets, starting left: 21 001 183 356
• we add 1 sets preceding ones "went on 999": 22 001 183 356

indeed, 21979182173/999=22001183 , remainder 356.

i've calculated complexity and, if i'm not mistaken, algorithm should work in o(n), n being number of digits of c in base b representation. i've done crude , unoptimized version of algorithm (only b=10) in c++, tested against gmp's general integer division algorithm , seem fare better gmp. couldn't find implemented anywhere looked, had resort testing against general division.

i found several articles discuss seem quite similar matters, none of them concentrate on actual implementations, in bases different 2. suppose that's because of way numbers internally stored, although mentioned algorithm seems useful for, say, b=10, taking account. tried contacting other people, but, again, no avail.

thus, question be: there article or book or aforementioned algorithm described, possibly discussing implementations? if not, make sense me try , implement , test such algorithm in, say, c/c++ or algorithm somehow inherently bad?

also, i'm not programmer , while i'm reasonably ok @ programming, admittedly don't have knowledge of computer "internals". thus, pardon ignorance - it's highly possible there 1 or more stupid things in post. sorry once again.

thanks lot!

---

further clarification of points raised in comments/answers:

thanks, - didn't want comment on great answers , advice same thing, i'd address 1 point lot of touched on.

i aware working in bases 2^n is, speaking, efficient way of doing things. pretty bigint libraries use 2^32 or whatever. however, if (and, emphasize, useful particular algorithm!) implement bigints array of digits in base b? of course, require b here "reasonable": b=10, natural case, seems reasonable enough. know it's more or less inefficient both considering memory , time, taking account how numbers internally stored, have been able to, if (basic , possibly somehow flawed) tests correct, produce results faster gmp's general division, give sense implementing such algorithm.

ninefingers notices i'd have use in case expensive modulo operation. hope not: can see if old+new crossed, say, 999, looking @ number of digits of old+new+1. if has 4 digits, we're done. more, since old<999 , new<=999, know if old+new+1 has 4 digits (it can't have more), then, (old+new)%999 equals deleting leftmost digit of (old+new+1), presume can cheaply.

of course, i'm not disputing obvious limitations of algorithm nor claim can't improved - can divide class of numbers , have priori know representation of dividend in base b. however, b=10, instance, latter seems natural.

now, have implemented bignums outlined above. c=(a_1a_2...a_n) in base b , d=b^k-1. algorithm (which more optimized) go this. hope there aren't many typos.

• if k>n, we're done
• add 0 (i.e. a_0=0) @ beginning of c (just in case try divide, say, 9999 99)
• l=n%k (mod "regular" integers - shouldn't expensive)
• old=(a_0...a_l) (the first set of digits, possibly less k digits)
• for (i=l+1; < n; i=i+k) (we have floor(n/k) or iterations)
  • new=(a_i...a_(i+k-1))
  • new=new+old (this bigint addition, o(k))
  • aux=new+1 (again, bigint addition - o(k) - i'm not happy about)
  • if aux has more k digits
    • delete first digit of aux
    • old=old+1 (bigint addition once again)
    • fill old zeroes @ beginning has digits should
    • (a_(i-k)...a_(i-1))=old (if i=l+1, (a _ 0...a _ l)=old)
    • new=aux
  • fill new zeroes @ beginning has digits should
  • (a_i...a_(i+k-1)=new
• quot=(a_0...a_(n-k+1))
• rem=new

there, discussing me - said, seem me interesting "special case" algorithm try implement, test , discuss, if nobody sees fatal flaws in it. if it's not discussed far, better. please, let me know think. sorry long post.

also, few more personal comments:

@ninefingers: have (very basic!) knowledge of how gmp works, , of general bigint division algorithms, able understand of argument. i'm aware gmp highly optimized , in way customizes different platforms, i'm not trying "beat it" in general - seems fruitful attacking tank pointed stick. however, that's not idea of algorithm - works in special cases (which gmp not appear cover). on unrelated note, sure general divisions done in o(n)? i've seen done m(n). (and can, if understand correctly, in practice (schönhage–strassen etc.) not reach o(n). fürer's algorithm, still doesn't reach o(n), is, if i'm correct, purely theoretical.)

@avi berger: doesn't seem same "casting out nines", although idea similar. however, aforementioned algorithm should work time, if i'm not mistaken.

your algorithm variation of base 10 algorithm known "casting out nines". example using base 1000 , "casting out" 999's (one less base). used taught in elementary school way quick check on hand calculations. had high school math teacher horrified learn wasn't being taught anymore , filled in on it.

casting out 999's in base 1000 won't work general division algorithm. generate values congruent modulo 999 actual quotient , remainder - not actual values. algorithm bit different , haven't checked if works, based on using base 1000 , divisor being 1 less base. if wanted try dividing 47, have convert base 48 number system first.

google "casting out nines" more information.

edit: read post bit quickly, , know of working algorithm. @ninefingers , @karl bielefeldt have stated more me in comments, aren't including in performance estimate conversion base appropriate particular divisor @ hand.