Bignum Challange

[Alrededor]

Duoas-
Regarding the problem of asymetrical range of values for positive and negative integers:

I was originally going to ignore the problem since the problem exists in the integers so why should I have to solve their problem. But since you wanted to deal with the problem I came up with the following solution in my long integer constructor. The integer constructor does the same type of thing.

BigInt::BigInt( signed long n ) : x_( sizeof( unsigned long ) * 8,
    ( n < 0 ? static_cast< unsigned long >( -( n + 1 )  ) + 1 : static_cast< unsigned long >( n ) ) ),
    negative_( n < 0 ? true : false )
{
    stripLeadingZeroes( x_ );
}

Note that x_ is the dynamic bitset whose constructor takes the number of bits as it first argument and an unsigned long as the second argument. The crucial part is:

( n < 0 ? static_cast< unsigned long >( -( n + 1 ) ) + 1 : static_cast< unsigned long >( n ) )

We add one to n, then negate the result which will be in the range of positive numbers, then use the static_cast to an unsigned long which is guaranteed to work. Adding one now increases the magnitude to what it should be.

Since -( n + 1 ) + 1 = -n this will also work for negative values whose magnitudes are within the range of permissible positive values. This works without any need to refer to std::numeric_limits <int> ::min(). It comes at the expense of performing the operations for all long int constructor calls. I am no expert so I don't know how expensive an operation the static_cast is (maybe just a compile time expense?), but the arithmetic operations above could well be register operations and hence very fast. I have done no comparison speed testing.

[Duthomhas]

Hmm, I hadn't thought of that. I'll have to check it out. Nice!

Also, I'll give your code the onceover and update the results if you like. :-)

[D80DSL3A]

YAHOOO!!

Since this thread got reactivated I thought I'd post to it again.
I've been working on a BigFloat class since the contest.
Just squashed a pesky bug about 5 minutes ago. Project went from partly working to working great right there!

First major goal achieved. PI to 52 places (as far as I know it) in 16 milliseconds. Will have to look up longer value now.

I used the power series for the arcSine(). Note: arcSine(0.5) = PI/6
so PI = 6.0*arcSine(0.5). The series gives the value to 52 significant figures in 80 terms.

For those interested, here is the version I wrote for double values:

double myArcSine(const double& x, const int& n )
{
	double sum = x;// retVal
	double a = x;// 1st term

	if( (n > 1) && (x*x < 1.0 ) )	
		for(int k=1; k<=n; k++)
		{
			a *= static_cast<double>(2*k-1)*(2*k-1)*x*x/static_cast<double>( 2*k*(2*k+1) );
			sum += a;
		}	

	return sum;
}

Using x = 0.5 it gives PI/6 to 12 digits precision in n = 18 terms.

[hamsterman]

Any reason 0.5? 2*arcSin(1) = pi too..
If you want to show someone power series, I'd suggest a wikipedia link...
http://en.wikipedia.org/wiki/Arcsin#Infinite_series
the "(2*k-1)*(2*k-1)*x*x/( 2*k*(2*k+1) )" might be hard to understand..

Also, how does your bigfloat work? Is it a 'bigfraction' or does it have the components of IEEE 754 floating point values?

[D80DSL3A]

@hamsterman. Yes, there is a reason for me not using x = 1. The series is convergent only for -1<x<1 which excludes the endpoint values x = -1 and x = +1.
Even if the endpoint were included I would use x = 0.5 because the series converges faster (approaches the exact value to a given precision in fewer terms) for lower values of x.

To get 12 digit accuracy from this function, the number of terms required grows fast with x:

arcSine(0.1) in 7 terms
arcSine(0.5) in 18 terms
arcSine(0.9) in 118 terms
arcSine(0.99) in 849 terms

My BigFloats are similar to big integers except that a decimal position is added as a data member. When adding (or subtracting), the digits are aligned at the decimal point position instead of at the least significant digit (the ones digit for an integer). When multiplying (or dividing) alignment of elements isn't needed but the position of the decimal in the result is given closely (but not exactly) by the sum (or difference) of the decimal positions in the operands.

A primary difference is this: The BigInts are intended to represent exact values, so their size (# of digits) grows with the value. A BigFloat is NOT intended to represent an exact value. It can't! For example, representing 1/3 = 0.333... requires an infinite # of digits. The size of a BigFloat is therefore arbitrary but FIXED, representing a value to a chosen # of digits precision.
In my BigInt class each instance has its own size (# of array elements) so Nele is a data member of each instance. In the BigFloat class, Nele is a static data member, so all instances share the same value. I did initial development with Nele =5 (so my floats are 20 digit numbers - still using base=10000 so I get 4 digits in each element). When I wanted PI to 52 places I just changed Nele to 15 so I could have 60 digit floats for that calculation.

I didn't provide a link or any explanation for how the function works because I didn't expect any interest. My previous posts of series based functions have fallen flat (even when the OP has asked for a method).

Lots of work left. Thanks for the reply.

[hamsterman]

The series is convergent only for -1<x<1

Right. Forgot about that..

Interesting choice of structure.
Though if I understand correctly, you have a maximum number of digits after the dot. That way this bigfloat seems not much different from a bigint.. IEEE style would decrease precision as number grows, which makes a lot of sense, since you may use that kind of float for both small and large numbers. Though both ways are not precise. Therefore it is unclear how much memory either part should use (pre-dot/past-dot or exponent/fraction). I myself would have probably chosen a fraction, since it can represent any rational number. Though of course there are irrational numbers.. But still, this way it is more clear, what needs to grow where.

[D80DSL3A]

hamsterman, regarding the position of the dot relative to the values being stored, I set it up a bit more flexibly than you may be picturing. I do have a maximum # of digits, but the dot can be located far before or after the significant values.

Example:
Suppose I have assigned const static int BigFloat::Nele = 3; Then for this case all BigFloats will store up to 3x4 = 12 digits (for the sake of a compact example).

If I enter this as a value for BigFloat z;
"0.000000123456" a 12 digit value (not counting the 0 before the . )

I don't get:
z.pEle[2] = 0, z.Pele[1] = 12, z.pEle[0] = 3456, z.Exp = -1

I get:
z.pEle[2] = 12, z.pEle[1] = 3456, z.pEle[0] = 0, z.Exp = -7

The dot lies before the start of the values recorded. I could store this number in a 3 element BigFloat:
"0.0000000123456789012" having 12 significant digits
I only store the significant digits:
z.pEle[2] = 1234, z.pEle[1] = 5678, z.pEle[0] = 9012

Then I indicate that the dot is 6 places to the left of the first digit with z.Exp = -7
So, I don't really have a maximum number of digits after the dot.

Rational numbers are great for most things, but PI is irrational!
My next function will be for finding square roots (many are irrational). It will be a good test of my functions to see how close the square of the result comes to the value I took the square root of!!

[Alrededor]

Duoas-
Thanks for offering to look over my code but don't feel obligated, since I didn't get my entry in by the deadline. I noticed that in my code on pastebin the expansion of tabs from 4 spaces to 8 spaces has really messed up the alignment of some of the comments that explained the algorithms. If it would help I will post a version with the tabs replaced by spaces. Also the comments on the flags used for i/o are a little misleading and could stand clarification.

In accordance with your statement:

Also, don't consider this the end of it all. Even if you did not participate in this challenge, you should try to make your own bignum anyway. It really is not that hard! Post back here as you go to ask questions or make suggestions, and have fun!

I may take a shot at a 16 bit base implementation. I have a few ideas for algorithms that are a little off the beaten track.

Thanks again for the challenge and the intellectual stimulation.

[hamsterman]

@fun2code
Oh. I see. So it does work like usual floats then. Though having a constant nEle still is not very flexible.
As for rational numbers, while pi or sqrt(2) are irrational, the members of the series expansion used to calculate them are, so we'd still get fine approximations of them. Just as fine as yours.

Speaking of pi, have you seen http://en.wikipedia.org/wiki/Pi#Computation_in_the_computer_age
I have a feeling those formulas are faster than arcsin(0.5)..

[cran]

I just did a large num class... I want to get a better multiply and divide before I go farther though... I think everyone should do one at least once, this has been a few for me. Not saying I have gotten any better... Oh, the link...

http://sourceforge.net/projects/lameutils/

I stuck it on sourceforge...

[cran]

fun2code (179) Dec 5, 2010 at 2:04pm
Thank you. I wasn't sure that my use of a bigger base would have that much of an effect on speed.
I'm working on a division method now, but it's not working out just yet...

the larger base effects speed a lot with larger numbers I think. You don't have to carry over to as many segments with a larger base... There was a question somewhere in the thread also, hold on... Eh, I can't find it. It was probably answered anyway...


Either way, sorry to post a link and run. I had to get offline right as I was putting that. I started doing LameUtils about the time this Challenge finished, so I didn't even have a chance. I did most of it when the internet was out and then when I got internet back, I touched it up a bit, but still haven't optimized anything. For the factorization, I used something that doesn't really speed things up much, but was interesting when I was trying to find a way to reduce the number of multiplies. Most everything was from memory, but I did look up the name for Newton's thing, since I actually remember learning that somewhere. I don't really know if the rest I came up with or remembered from something while I was trying to find a way to do it. I know the multiplication was from something I learned also, but still haven't looked it up. The division was pure messing around and spaghetti code that turned out to be faster than it looks, even though there are faster algorithms out. The factorial and power and the public log2 functions were added recently and would have been sooner if I didn't spend so much time trying to find a different way to do factorial.

Either way, I made it work on g++ as well and wrote some things while on the linux box, but most of it I wrote in windows... I can't seem to get off of the MS crack... Either way, I want to optimize the output first, because that's slow as hell for larger numbers, and then the multiplication, because almost everything hinges on that. I was looking at the ones out now.. Wow, that will take some time to figure out. I don't like to code things I don't understand (even though I've done it). Well, I understand it in part, but overall it's still confusing. For now, I'm going to fix it up as is and worry about the rest later... I hope that someone can use it, or that by putting it online, I won't get the urge to do it yet again...

[Duthomhas]

I'm dinking with (input) serialization now, because for really big numbers I want to avoid playing with huge temporary strings and slowness from large divisions for the base conversion...

Here is my strategy (yet to implement, because I'm writing division now ;-)

Use some math to determine the number of bigits that are an even multiple of <radix to output>. So if I am printing in base ten, I need the number of bigits that contain a number evenly divisible by ten. Simple.

Next, split the number, one piece at a time, into chunks that size, starting with the most significant digits (which may have a piece smaller than the others -- if there are others).

Transform that piece, using normal bignum division and remainder, into a string representing that piece. Output that string.

Repeat until the number is exhausted.

This will reduce the number of operations needed to do the base conversion significantly.


In any case, I was thinking about continuing with some postings about optimized multiplication techniques....

[cran]

Yeah, I need to really improve the output, but that was kind of made as an after-thought... That reminds me, I actually starting with the strings, then the array, then the numbers last... either way, back on subject. That's assuming that the number can split, if it's a huge prime, then you'll have to find another way, I think. I'm not sure it'll help though, because getting the output for a piece oh, wait... saying it, I think I see what you mean. It's still a pain in the butt...

I need to put more thought into the output... I'll think on it and post something, but for now, I should already have been asleep...

[cran]

actually, now that you said it... I could just convert it in the same primary except with a radix of 10*n that fits into the base (since I kind of already do that) and then convert to char and output on the fly from there... that might speed things up a little.

[Duthomhas]

You've got it. The primality of the number is irrelevant. We're not factoring the number, just splitting it at convenient powers, much like you do when writing really big ones on paper: 12,345,678.

[edit] Hmm, you posted back before I hit submit. You are thinking of what is called "rearrangement". I avoid that because it still requires creating, basically, a copy of the number that uses more space than normal.

(Sorry for the delay.. I'm multitasking here...