|
Long Division / Assembly Language Style
I am a little bit embarrassed that I can't figure this out on my own with pencil and paper; in fact, a lot embarrassed
MY QUESTION...
What is the Algorithm for dividing one very large integer by another ?
I don't want to get too ridiculous on my first attempt at this, so I will toss out these sorts of values...
TWO UNSIGNED INTEGERS
- A Thirty-Four Byte Dividend
- A Seventeen Byte Divisor
In bits, that would be
- A 272 Bit Dividend
- And a 136 Bit Divisor
I want to do this using All_Or_Mostly 8-Bit registers to the maximum extent possible.
I am quite surprised that I couldn't find this question answered with a web search.
Can someone tell me what question to ask Google ?
For that matter, is there a better online community than this one for questions such as this one ?
I am totally fine if we start off learning how to do 16-bit division using 8-Bit regs and then move up to 24, 32, 40, 48 etc. dividend sizes
|
|
|
|
|
|
Are you building it on top of an instruction like x86's div, which takes a double-width dividend and a regular-width divisor, and results in a quotient and remainder? Or some other, less convenient, type of division (like MIPS) which divides two equal-sized numbers by each other?
Or is it a from-scratch kind of deal, on a machine without division?
|
|
|
|
|
Have you considered table lookup?
No smiley ... In the days when a CPU filled a rack of boards, and the ALU (Arithmetic/Logic Unit) alone was a least one board, maybe more, there was a machine that did that, although for floating point rather than integer. The most significant bits of the mantissas (always kept normalized, with a hidden MSB) were used as indexes into a huge 2D table in ROM, giving the 11 most significant bits. From that, a Newton iteration was done, doubling the precision for each iteration. The entire iteration was done in hardware: The initial lookup took one clock cycle, each iteration took an extra clock cycle (two for single precision, four for double precision). The final normalization of the result took yet another clock cycle.
This FP divide was so fast that the CPU didn't have any integer divide logic. It was faster to convert the integers to 64 bit FP, do the division and convert back. The FP logic alone was a circuit board about A3 size (i.e. twice the size of a standard typewriter paper) packed with chips.
For all I know, maybe modern CPUs use the same technique today. In the late 1970s, it was so remarkable that the design was presented in internationally recognized professional magazines.
If I were to write a division function for arbitrary length integers (or arbitrary precision float), I would consider seriously something in this direction. If the machine provides a division instruction, you can use that to obtain the first 'n' bits, rather than using a huge lookup table.
|
|
|
|
|
 Interesting history! I'd never heard of this.
|
|
|
|
|
|
Quote: What is the Algorithm for dividing one very large integer by another ?
The first idea that come to mind is the same algorithm that is used by hand, a bunch of subtractions and shifts.
Long subtractions and long shifts are easy in machine language.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
I'm trying to create/solve a puzzle in which you are given tetris-like cages in which digits will be placed but cannot have 2 digits in the same row or same column. The goal is to determine the possibilities of doubles and triples [doubles,triples] for a given cage.
For example, with the cage
[[0,1]
[1,1]]
in which 1's indicate cells in the cage, up to 1 double ([1,0]) is allowed.
The restrictions for the cage input is it has a max width of 8, a max height of 3 and max size (# of 1's) of 8.
Here are some more examples along with there possible outputs:
[[1,1],
[1,0],
[1,0]]
[[1,1],
[1,1]]
[[1,1],
[1,0],
[1,1]]
[[1,1,1],
[1,0,0],
[1,0,0]]
[[1,1,0],
[0,1,1]]
[[1,1,0],
[0,1,0],
[0,1,1]]
[[1,0,0],
[1,1,0],
[1,1,1]]
[[1,1,1],
[1,0,1],
[1,0,1]]
[[1,1,1],
[1,0,1],
[1,1,1]]
Please reach out with any questions. I appreciate the help figuring out how to do this programmatically!
|
|
|
|
|
It's far enough removed from reality that no one seems to care.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
Figured it out. The key was recursion.
|
|
|
|
|
Program-1:
for (i = 0; i < m, i + +){
for (j = 0; j < n, j + +){
if (a = b){
arr[i][j] = 1;
}
else{
arr[i][j] = 2;
}
}
}
for (i = 0; i < m, i + +){
for (j = 0; j < n, j + +){
arr[i] += arr[i][j];
}
}
for (i = 0; i < m, i + +){
if (a = b){
p[i] = i
q [i] = i
}
}
Program-2:
for (i = 0; i < m, i + +){
sum = 0;
for (j = 0; j < n, j + +){
if (a = b){
arr[i][j] = 1
sum += 1;
}
else{
arr[i][j] = 2
}
}
if (c = d){
arr[i] = sum;
p[i] = i
q [i] = i
}
}
I tried to make a time complexity equation.
for program-1:
m*n*c1 + m*n*c2 + m*c3
for program-2
m*n*c1 + m*c2
which one is better and how much? Could you please help on that?
|
|
|
|
|
|
|
You need to account for the "number" of "for loops" also; the total iterations might be equivalent, but not the "setting up and tearing down."
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
I need a routine that will generate a random names for files and folders. As long as they are valid file/folder names it doesn't matter what it is.
I have been thinking up several different ways to do this, but I'm wondering what the community thinks is the best way to do this.
I thought about the Windows API that generates a unique temporary file, but technically that file is unique only within the temp directory.
I thought about generating Guids, but that seems to be frying an egg with a nuclear reactor.
What do you think?
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Richard Andrew x64 wrote: I thought about generating Guids, but that seems to be frying an egg with a nuclear reactor.
What do you think?
I think you are wrong. Using Guids is simple enough and has nothing to do with something like "a nuclear reactor".
|
|
|
|
|
Yes I guess you are right.
Thank you for your response.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
I want to calculate the time complexity and show by the equation for both algorithms. Also, I need a comparison between the two algorithms to show which one is better and why. Could you please help with that? It would be beneficial for me and very much appreciable.
Algorithm-1
--------------------------
1.for 1 to m
for 1 to n
if (some condition)
do something
else
do something
end for
end for
2.for 1 to m
for 1 to n
do something
end for
end for
3.for 1 to m
if (some condition)
do something
end for
4.do something
5.for 1 to m
for 1 to m
if (some condition)
do something
end for
end for
6.for x to y
for 1 to x
if (some condition)
do something
end for
end for
Algorithm-2
--------------------------
1.for 1 to m
for 1 to n
if (condition)
do something
else
do something
end for
if (condition)
do something
end for
2. do something
3.for 1 to m
for 1 to m
if (condition)
do something
for 1 to x
if (condition)
do something
break
end for
if (condition)
do something
end for
end for
Thanks, Advance
|
|
|
|
|
Help how? You could answer the question yourself by coding the two algorithms and running some tests.
|
|
|
|
|
Thank you Richard MacCutchan for your response. I have to prove by equation that one is better than other and how much better. I need help on that. You may can help me for that.
|
|
|
|
|
Benchmarking is not to determine algorithmic complexity.
It can be used to confirm that your theoretically determined O() is correct, but a few timing values is not an O().
To the OP: In my studies, algorithmic complexity was the sole subject of a quarter-long course. The textbook was a few hundred pages long. I don't remember if I took it during our junior or senior year; in any case, we were quite experienced programmers then, and had completed courses in related subjects like statistics and queue theory. The foundation was in place.
If you want to learn how to determine the algorithmic complexity in general, you may have a long path to walk. There may be quick and easy answers to specific, simple, algorithms (an experienced guy can pop an O() right out of his head for the examples you present), but you would benefit from learning more general methods for complexity estimation.
And: If you are doing timing benchmarks, make sure to test over a broad range of input - here: in terms of problem size. With small problem sets, initial setup, reporting etc. can make up a large part of the time consumed. Also, be very much aware of compiler optimizations. Some compilers are clever shortcutting loops etc. in a way that may severely affect timings. It may be safer to turn all optimization off. (Actually, for verifying a theoretical O(), you might come better out by adding counters to your code in appropriate places, rather than measuring execution times!)
|
|
|
|
|
Why are you telling me this? You need to reply to the OP.
|
|
|
|
|
because you seem to suggest to the OP that "coding the two algorithms and running some tests" can serve as a replacement for an analytic complexity determination.
Besides: What is posted in a public forum is not directed at you alone, but to all readers of the forum.
|
|
|
|
|
All I said was, "You could answer the question yourself by coding the two algorithms and running some tests.". I left it up to the OP to decide if that was what he wanted. But either way, it is unlikely that OP will read your message, so missing some useful information.
|
|
|
|
|
Member 11512486 wrote: Could you please help with that? It would be beneficial for me and very much appreciable.
Sure! Hope the below would help.
Start by learning about complexity: Understanding Time Complexity with Simple Examples - GeeksforGeeks
Then, have a look at something like: How to analyze time complexity: Count your steps · YourBasic
There are many more material online in case you need more info to understand what it means and helps.
Overall,
1. code a sample doing same problemX using algorithm 1 & 2
2. compare the time taken for both to solve that problem with multiple set of inputs (increasing)
3. you can also compare the space used by both and use as another comparing parameter
Try out!
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
