so take integer 123456789123456789 as this set ar[0] = 9 set ar[1] = 8 set ar[2]

Question

so take integer 123456789123456789 as this

set ar[0] = 9
set ar[1] = 8
set ar[2] = 7
set ar[3] = 6
set ar[4] = 5
set ar[5] = 4
set ar[6] = 3
set ar[7] = 2
set ar[8] = 1
set ar[9] = 9
set ar[10] = 8
set ar[11] = 7
set ar[12] = 6
set ar[13] = 5
set ar[14] = 4
set ar[15] = 3
set ar[16] = 2
set ar[17] = 1

And integer 123456789123 as this

set ar[18] = 3
set ar[19] = 2
set ar[20] = 1
set ar[21] = 9
set ar[22] = 8
set ar[23] = 7
set ar[24] = 6
set ar[25] = 5
set ar[26] = 4
set ar[27] = 3
set ar[28] = 2
set ar[29] = 1

Consider that the two arrays are linked lists with pointers next and prev and a dummy head with boolean head set to true.


How would you do 123456789123456789/123456789123 without any overflow while only using of 32 bit signed integers? Be sure to also return the remainder. Please provide a fast solution that guarantees that there will never ever be overflow no matter what happens ^)^.


You will have to store the remainder in an array (linked list) as well.



Subtracting continuously is not a solution. Guessing a quotient and then subtracting continuously is not a solution either as large numbers will require too many subtractions. Using boolean division is not a solution either >: o.


The integers may be stored using any word size (base) as well. I personally use 32768 to protect against overflow in fast multiplication =).


May not declare arrays on the fly, may not pass or return pointers unless they are like a pointer to a linked list or a string, may not use strings for storage, may only use single dimensional arrays. Only basic operations allowed are +, -, *, /, =.


Tx ; D



If this helps, here is my current division algorithm (I know that I need to store the remainder m in a linked list as well... it's overflowing, hehehe)

private static method divide2 takes nothing returns boolean
local integer d = toBeDivided //BigInt that is to be divided
local integer i = toDivide //number doing the dividing
local integer m = 0 //remainder

loop
loop
set d = p[d] //go to previous digit
exitwhen h[d]

//exitwhen remainder (numbers being pulled out of BigInt) is bigger than number doing the dividing
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"m = "+I2S(m)+"*"+I2S(BASE)+" + "+I2S(v[d]))
set m = m*BASE + v[d]
if (0 > m) then
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"ERROR")
return false
endif
exitwhen m >= i
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,"exitwhen "+I2S(m) + " >= "+I2S(i))

//! runtextmacro BIG_INT_REMOVE("d")
//! runtextmacro BIG_INT_DEALLOCATE("d")
endloop

exitwhen h[d]

//in this case, remaining digits will always be < base
//! runtextmacro BIG_INT_GET_REMAINING_DIGITS("v[d]", "m", "i")
//! runtextmacro BIG_INT_GET_CURRENT_DIGIT("m", "m", "i")
endloop

set dmod = m

return true
endmethod
method divide takes integer divisor returns integer
if (1 < divisor and not h[n[this]]) then
set toBeDivided = this
set toDivide = divisor
call TriggerEvaluate(divt)
return dmod
endif
return 0
endmethod


globals
h = head
n = next
p = prev
v = value of digit

toBeDivided, toDivide, and dmod are globals


Here are the macros I used
//! textmacro BIG_INT_REMOVE takes THIS
set n[p[$THIS$]] = n[$THIS$]
set p[n[$THIS$]] = p[$THIS$]
//! endtextmacro
//! textmacro BIG_INT_DEALLOCATE takes THIS
set n[$THIS$] = n[0]
set n[0] = $THIS$
//! endtextmacro
//! textmacro BIG_INT_GET_REMAINING_DIGITS takes THIS, TO_POP, BASE
set $THIS$ = $TO_POP$/$BASE$
//! endtextmacro
//! textmacro BIG_INT_GET_CURRENT_DIGIT takes THIS, DIGITS, BASE
set $THIS$ = $DIGITS$ - $DIGITS$/$BASE$*$BASE$
//! endtextmacro


GET_CURRENT_DIGIT is mod
GET_REMAINING_DIGITS is just division of ints
DEALLOCATE deallocates to a stack using next pointer and 0 (0 used never used)
REMOVE just removes from the list

Here are some more
//! textmacro BIG_INT_ALLOCATE takes THIS
if (0 == n[0]) then
set $THIS$ = ic + 1
set ic = $THIS$
else
set $THIS$ = n[0]
set n[0] = n[$THIS$]
set v[$THIS$] = 0
endif
//! endtextmacro

ic is instance count

//! textmacro BIG_INT_INIT_HEAD takes THIS
set n[$THIS$] = $THIS$ //next
set p[$THIS$] = $THIS$ //prev
set h[$THIS$] = true //head
//! endtextmacro

this initializes a linked list (circular).

//! textmacro BIG_INT_ENQ takes THIS, PREV, NEXT
set p[$THIS$] = $PREV$
set n[$THIS$] = $NEXT$
set p[n[$THIS$]] = $THIS$
set n[p[$THIS$]] = $THIS$
//! endtextmacro

This just places a node between the nodes PREV and NEXT.


This was written using vJASS ;o, which is sort of an extension of JASS for Warcraft 3. JASS has a nasty op limit count, hence why I have TriggerEvaluate in there. TriggerEvaluate sort of appends a new thread to the current thread, thus preventing op limit count from being hit ^)^. Don't worry about op limit stuff, I'll deal with that all : ), so just use functions normally (no weird trigs needed).


At this point I need to add so much to the division algorithm to account for the remainder overflows that I'm just ready to see if I can possibly divide by numbers greater than 2^31-1 =).

There are no longs in the language.. stuck with ints. Also, the remainder will need to be stored in a linked list (it's own BigInt thing). You can use the methods add and multiply freely -> bigInt.add(50), bigInt.multiply(50). You can also use addBig and multiplyBig freely -> bigInt.addBig(bigInt2), bigInt.multiplyBig(bigInt2). I'll inline them myself to keep speed up (appending threads is huge overhead, so have to inline everything to keep the thing from freezing >.<).


This will usually handle numbers around 240 digits in Base 82, but I want it to be able to handle digits up to like 8k. The arrays have 8192 indexes from 0 to 8191 and you can't decide how big you want the array to be... it's just stuck that way.

globals
integer array hi
endglobals

example of integer array. Everything auto initialized to 0 ^)^.

globals
boolean array boo
endglobals

example of bool array. Everything initialized to false.

globals
integer i = 0
endglobals

example of a plain integer.

Local variables can only be declared at the top of the function.

function hi takes nothing returns nothing

local integer array boo
local integer i = 3

set boo[i] = i*2

endfunction



That's all : ). Tx for your time ^^. If you decide to help, tx for your help too ; D.

 

 

I also know that this is a pretty unreasonable thing to ask for help on. I've just been struggling with trying to figure out a good way to do it for a very long time and coming here is sort of a last resort ;o. Nobody's been able to help with this ; (.

Explanation / Answer

the program is given as: #include #include // or "ctime" #include // for #include // Windows stuff #include // GOD DAMMNIT WINDOWS WHY???? #include // Ncurses #include // STL stuff #include #include

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.