|
Hi all.
I am David and I am writing "big integer" class. In my class I use "long long Number[_NUMBER]" ( in C++) and I need algorithm of division,
it is not problem if this algorithm will use bit set and not "long long" type, I need that it was fast. In other words I need algorithm that divides one vector onto another
this vector can be vector of bits ( Ex: [1, 1, 1, 0, 0, 1, 0, 1, 0, 1] ) or vector of number ( Ex: [1258, 16546, 54646846, 54685, 088946, 555468, 8864, 11213, 1] )
Thanks for any help.
|
|
|
|
|
You could check out libGMP (GNU Multiple Precision Library), which is Open Source (zlib-licensed, IIRC) and does the same thing.
Alternatively, you could model the thing by re-implementing what you would do when you divide one number by another. Just do some divisions and model those steps. That, however, probably is not the best way to do divisions. You should check the "Math"-Forum for better algorithms.
|
|
|
|
|
I apologize. I missed the fact that you already posted this in the Math-Forum.
Thats what you get when you usually only read the VC-forums.
|
|
|
|
|
I'm working on a similar class LongMath.
Have you had any luck with division?
I've completed add, subtract and multiplication of negative/position whole and non-whole numbers but have been stuck on the division. I can divide negative/positive numbers but only whole numbers and I'd like to compare notes. Interested?
|
|
|
|
|
"Interested?"
Yes I am.
About your problem:
Use integer division for your non integer Number.
Ex:
121/11 = 11 if 1.21/11 = (121/11)*0.01
or
14/3 = 4+2/3 = 4+(20/3)*0.1 = 4+(6+2/3)*0.1 = 4+(6+(20/3)*0.1)*0.1=
=...=4+0.6+0.06+0.006+0.0006+.....
it is idea and math.I hope you like this.
Can you send my division algorithm?
|
|
|
|
|
I'll apply the above to my class and I'll email you my source or I'll email you a link to it.
Class Diagram::LongMath
<span style="width: 10px;"></span>Addition <br />
<span style="width: 20px;"></span>Add(sourceA <font color="#0000ff">As String</font>, sourceB <font color="#0000ff">As String</font>) <font color="#0000ff">As String</font><br />
<span style="width: 10px;"></span>Subtraction <br />
<span style="width: 20px;"></span>Subtract(sourceA <font color="#0000ff">As String</font>, sourceB <font color="#0000ff">As String</font>) <font color="#0000ff">As String</font><br />
<span style="width: 10px;"></span>Multiplication <br />
<span style="width: 20px;"></span>Multiply(sourceA <font color="#0000ff">As String</font>, sourceB <font color="#0000ff">As String</font>) <font color="#0000ff">As String</font><br />
<span style="width: 10px;"></span>Division<br />
<span style="width: 20px;"></span>Divide(divisor <font color="#0000ff">As String</font>, dividend <font color="#0000ff">As String</font>) <font color="#0000ff">As String</font><br />
This may take me a few days with the holidays here and all.
|
|
|
|
|
|
Hi,
I was playing around with a BigInteger class recently and so have come across the same problem.
The fastest way I could think of is below, if you say x / y = z (with remainder = r).
1. Find the leading 64 bits of your big number (x)
2. Find the leading 32 bits of your divisor (y).
3. Divide (1) by (2) to give you the leading 32 bits of z.
4. Multiply (3) by y and take this number from x
Continually applying steps 1-4 reduces the size of x until you are within +/- 1 of the correct value of z.
This is fast because all operations are O(n) or less if you code them properly!
Hope this is of some use & good luck!
Russ
|
|
|
|
|
Hi, I can't help specifically with c++ code to do long division .. but I wrote code in vb to do arbitrary precision floating point math.
The division method that I used turned out to be suprisingly fast and much easier to implement than addition or subtraction with signed floating point numbers.
The method is called the Newton-Raphson method or just Newton's method. I won't go into it here, just search for it, you'll find numerous examples.
I don't know how well it would would with integers only since the method uses multiplication, addition and subtraction iteratively but principal is sound anyway.
The guts of the divide method I wrote is this:
Do While Compare <> Guess
Compare = Guess
Guess = Left(Multiply(Subtract("2", Multiply(y, Guess)), Guess), Precision)
Loop
If your multiply, add and subtract methods can handle large numbers (this one uses strings) and you provide code to prevent the length of the result with each iteration from getting too long then sometime like may work. Each iteration will double the accuracy.
With another 50 or so lines of code this method can divide numbers thousands of digits long in milliseconds.
I also read somewhere where the Newton method is the fastest for divison.
|
|
|
|
|
i want to develop a website that contains a searching function on it, i'm using visual web developer as a machine and SQL server as a database,
i need to know about binary search, can anyone help me with the concept of binary search and how its work...?? i will really thankful...
-thank you-
|
|
|
|
|
MaSTaMaRViN wrote: can anyone help me with the concept of binary search
Google didn't turn up anything? 
The evolution of the human genome is too important to be left to chance.
|
|
|
|
|
MaSTaMaRViN wrote: can anyone help me with the concept of binary search and how its work...??
It's much like searching for a name in the phone book. You start in the middle. If the name you are searching for is less than the current name, you can eliminate the right half of the phone book. If the name you are searching for is greater than the current name, you can eliminate the left half of the phone book. You now do the same search again, each time reducing the set by half. This is a very high-level observation.
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
What you say is true at a high level, however searching for a name in the phone book is really more like interpolation search[^]. For example, if you know the name starts with 'B', then you can start much closer to the beginning than the halfway point. However, as the article states, the extra computation needed to find where to look often makes interpolation search not faster than binary search.
--
Marcus Kwok
|
|
|
|
|
Hello all,
I have created a sorting algorithm that is better than Quick Sort and even competes with Introspective Sort, but is constructed in a much simpler way.
I would like people to scrutinise the code, it is rather simple and shouldn't take long to look through. I want to know what people think of it. I have freely released the algorithm for anyone to use and develop further.
Please go to the following link to find out more:
http://www.geocities.com/nicemadnicemad/software.html
Thanks.
Chris Nash
Find the simplest proof and you have the ultimate truth.
|
|
|
|
|
A description of the algorithmm, and what makes it different from quicksort, would be nice (trawling through other peoples C sources isn't exactly a fun thing to do)
Developers, Developers, Developers, Developers, Developers, Developers, Velopers, Develprs, Developers!
We are a big screwed up dysfunctional psychotic happy family - some more screwed up, others more happy, but everybody's psychotic joint venture definition of CP
Linkify!|Fold With Us!
|
|
|
|
|
|
intrepid_is wrote: I have created a sorting algorithm that is better than Quick Sort...
How so?
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
I looked at it (even though he found "better experts" ha!  ) As I understand it, he needs knowledge of the smallest and largest value, so he has a better partitioning at quicksort.
Developers, Developers, Developers, Developers, Developers, Developers, Velopers, Develprs, Developers!
We are a big screwed up dysfunctional psychotic happy family - some more screwed up, others more happy, but everybody's psychotic joint venture definition of CP
Linkify!|Fold With Us!
|
|
|
|
|
Hello,
I'm a newbie in computer programming.
I'm looking for a program help me to change file attributes(Created time,Modified time and last access) like FileDate By T.YogaRamanan.
Here is link :
http://www.codeproject.com/file/FileDate.asp[^]
But I want to ignore its user interface.(No Dialog box , No Text box)
I want to choose file as coding and change file attribute as coding too.
I have tried to read source code of FileDate above.
I still can't do.
Can you help me ? 
Thank you.
|
|
|
|
|
This is not the right forum for your question. And dont re-post same topics all over the place.
"A good programmer is someone who looks both ways before crossing a one-way street." -- Doug Linder
coolestCoder
|
|
|
|
|
Hi guys,
I 'm a student of computer science from Indonesia
and newbie in vb6 programming. please, help me to
learn the algorithm of vb6. the following is algorithm
question.
1) Present the prime number between 1 up to 10 that use
"Mod" and "Print" function. the Object is only 1 command
button.
Note: forbidden use "int" function
thank's for helping me.
your sincerely
IRWAN
i need help in vb6 algorithm
|
|
|
|
|
Which part don't you understand? Ask a specific question, otherwise people here aren't going to do your homework for you.
The evolution of the human genome is too important to be left to chance.
|
|
|
|
|
Tim Craig wrote: people here aren't going to do your homework for you.
I find it amazing how many people don't seem to get the clue 
|
|
|
|
|
PaulC1972 wrote: I find it amazing how many people don't seem to get the clue
Lately it seems like most of them come from third world countries where the powers that be want to ship US jobs. They're too lazy to even try to do their homework and they get rewarded for it.
The evolution of the human genome is too important to be left to chance.
|
|
|
|
|
Maybe so on this site... have you recently checked Rent A Coder? I see a lot of US students posting homework questions there...
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
