Newton-Raphson division for a non-binary base?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

sgfw
Posts: 46
Joined: Wed Jun 19, 2013 11:47 pm UTC

Newton-Raphson division for a non-binary base?

Postby sgfw » Thu Oct 16, 2014 8:12 pm UTC

I'm trying to make an arbitrary precision float class in C++, and it stores the information in a linked list of unsigned integers as digits in base 4294967295. I chose this number because I thought it was a good number as far as processing required for an operation vs. memory efficiency. I have made operations to add, subtract, multiply, and divide, but the division algorithm I used is extremely slow, so I want to rewrite it with the Newton-Raphson algorithm. However, everywhere I look, the divisor is bit-shifted to be between 0.5 and 1. That's fine and dandy for binary, but bit-shifting isn't as easy in base 4294967295. Is there a way I can get around that?

Thanks.

jareds
Posts: 436
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: Newton-Raphson division for a non-binary base?

Postby jareds » Fri Oct 17, 2014 3:38 am UTC

I don't understand why you're using base 4294967295 and not base 4294967296.

That said, you can still scale things into the range of [1/2, 1). Let R=4294967295. First, scale things into the range of [1/R, 1). So, your divisor's most significant digit is N, where 1<=N<R, and your divisor is X, where N/R<=X<(N+1)/R.

Multiplying X * floor(R/(N+1)) will be < 1, because X < (N+1)/R and floor(R/(N+1))<=R/(N+1). With basic algebra, I can prove that that will be >= 1/2 if N^2 - (R/2) * N + R/2 <= 0. Also, it will obviously be >= 1/2 if N >= R/2.

In your case, this just leaves N=2147483647 and N=1. Obviously, in the first case you need to multiply X by 2 iff X < 1/2. In the second case, you need to multiply X by 2147483648 if X < 1/2/2147483647 and by 2147483647 if X >= 1/2147483648. However, 1/2/2147483647 < 0.[1][2] (base R) and 1/2147483648 > 0.[1][4294967293] (base R), so you have a huge amount of leeway. (That is, as long as you multiply by 2147483648 when the next digit is 0 or 1 and by 2147483647 when the next digit is 4294967294, you'll be fine.)

And note, by the way, that scaling to the range of [0.5, 1) is only necessary if you want to use an initial linear approximation and number of iterations that were designed for that range. You can do Newton-Raphson with a different linear approximation and/or a different range of initial values--you would just need to work out the maximum initial error so that you know how many iterations to do.

sgfw
Posts: 46
Joined: Wed Jun 19, 2013 11:47 pm UTC

Re: Newton-Raphson division for a non-binary base?

Postby sgfw » Sat Oct 18, 2014 7:48 pm UTC

Thanks! Also, I'm using base 4294967295 instead of 4294967296 because an unsigned integer in c++ can't hold 4294967296, because it would take 33 bits. I could store it in an unsigned long, but that would be inefficient.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Newton-Raphson division for a non-binary base?

Postby jaap » Sun Oct 19, 2014 12:54 am UTC

sgfw wrote:Thanks! Also, I'm using base 4294967295 instead of 4294967296 because an unsigned integer in c++ can't hold 4294967296, because it would take 33 bits. I could store it in an unsigned long, but that would be inefficient.

I don't understand what you are saying here.
Just as base 10 uses digits 0 to 9 and has no digit symbol with value 10, base 4294967296 uses digits 0 to 4294967295, exactly the full range of what an unsigned 32-bit integer can hold, and never needs any digit to hold value 4294967296.

sgfw
Posts: 46
Joined: Wed Jun 19, 2013 11:47 pm UTC

Re: Newton-Raphson division for a non-binary base?

Postby sgfw » Sun Oct 19, 2014 3:51 pm UTC

Just as base 10 uses digits 0 to 9 and has no digit symbol with value 10, base 4294967296 uses digits 0 to 4294967295, exactly the full range of what an unsigned 32-bit integer can hold, and never needs any digit to hold value 4294967296.


Oh, I guess you're right. I lost track of the reason I am using base 4294967295 a bit. I am actually using it because there are tons of operations that involve the exact base, such as with subtraction in base 10, there are many times when one must add 10 to a digit, and I wanted to use the same data type. Sorry about that, I guess I got confused. In case you're wondering how someone could possibly forget their reasoning in selecting a base, it is because I was using base 4294967296, but then I got to making some operators, and ended up realizing that it would be easier to use 4294967295. I then promptly forgot about that incident and went along not putting much thought into it.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 6 guests