Tag Archives: c++

Working With Big Numbers

Recently a friend asked me a some questions:

“97 raised to the power of 242 has equalled infinity on every calculator I’ve used, but it’s not infinite just very big. Why do they say infinity? And what is 97^242?”

The answer to the first part is easy; precision (and hence maximum values) are limited. Since this isn’t a basic intro to binary and computing we won’t go into it but just say in the good old days this would have resulted in the number simply wrapping. Modern devices and systems detect this overflow and show a special case result, usually Infinity/Inf or sometimes Not-a-Number/NaN.

Big number calculation in R

97^242 in R

96^242 in Matlab

97^242 in Matlab

Above are two common tools (R and Matlab) both running on 64-bit Linux and overflowing for 97^242. The difference in overflow can be seen in that the OSX Calculator can handle 97^71 but overflows at 96^72, whereas both Matlab and R will handle 97^166 but not 97^156.

Ok well Google has a calculator function so maybe we can just ask it for 97^242?

Google for 97^242

Google for 97^242

Alas, no. But maybe if we trick it with 97+242 to get it’s calculator up and then use that?

Google calculator

97^242 in Google Calc

Nope. So how do we go about trying to calculate 97^242?

There are approaches we can use to estimate it (one of the most promising being looking for differences between powers of 100 and 97 then extrapolating, maybe something for another blog post) but we want an exact answer. As shown by Matlab/R and common logic built-in types are just too small and will overflow.

The solution comes, as with so much in life, from GNU in the GNU Multiple Precision Arithmetic Library aka GNU MP Bignum.

Once installed (yum install gmp-devel on Fedora) it’s just a case of hacking together some C to calculate the result (note the below isn’t supposed to be efficient, more transparent):

#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>

int main(int ac, char** av)
{
	mpz_t number,start;
	unsigned long int startnumber = 97;
	int i=0;
	mpz_init(number);
	mpz_init(start);

	mpz_set_ui(start,startnumber);
	mpz_set(number, start);

	for (i=0; i<(242-1); ++i)
	{
		mpz_mul(number, number, start);
	}

	gmp_printf ("Answer: %Zd\n\n", number);

	return 0;
}

Build this with: gcc bignum.c -lgmp -o bignum

And voila:

Answer: 6291579554172660514180168586029512181759771859911909633079235697774386086528343277488812886056338013920280508647975158853848809035553070842805751211101339655910548731303652360707362342079349547320620109301210997985503312350525910702941569606402987567610468491227904389508486082138580406254059512446817845870945561908178074689723504831108854735558785367285467641732532222094514773911007516550984383178257067496267923472962067697340265687768345831925754550553895144516227499602812609

Which for those who can’t be bothered to count digits is rounded as 6.29E+480.

Though of course after all this loading of libraries and writing of C it turns out that although Google couldn’t answer it, naturally Wolfram|Alpha could:

Wolfram Alpha Calculation

Wolfram|Alpha Calculates 97^242 with Ease!

Variable Length Arguments in C++, Java, and PHP

Normally in software development we define methods with a given number of parameters (and their type in some languages). Quite often however we want to be able to deal with different numbers of arguments and there are two widely used approaches; different methods and default parameters.

Different methods relies on the concept that the call to function is matched not just on the name of the method but also the count (and type if applicable) of the parameters. So if we wanted a method that could accept one or two integers in C++ we could define two methods:

void SomeFunction(int);
void SomeFunction(int, int);

So if we called SomeFunction(1) the first would be used, SomeFunction(1,2) would use the second.

Default parameters allows us to define some of the parameters as optional and their default values if not passed so the definition:

void SomeMethod(int a, int b=0);

Would accept one or two integer parameters. SomeMethod(1,2) would have a=1 and b=2 whereas SomeMethod(1) would use the default value and so b=0.

This is all very good and highly useful in a variety of situations but suppose you wanted to handle any number of parameters, from a very small set (or zero) to a large number. Using either of these techniques would require a lot of additional coding, creating a method for each length or the longest set of default parameters imaginable.

This is where the concept of variable length arguments for a method comes in; we want to be able to define a method and accept an arbitrary number of arguments which it can process (please note in most if not all cases the best option for this would be to pass something like a Vector in C++ or an array in PHP, but best practice is not the point of the exercise).

Let’s consider a problem.

We want to have a LineShape function. This function takes a series of Points (a simple class just containing an X and Y coordinate). In a proper system it would then start with the first point and draw a line to each consecutive one but for our example we just want it to print a list of the points it will draw to/from in order.

This could be two points (a single line) or a complex shape of an undetermined total number of points (again note the caveat above that a Vector/List/Array would be the best and safest way to do this in TRW).

So for our implementation we need:

  • A simple Point class
  • A method (LineShape) that takes an arbitrary number of Points and prints out the coordinates
  • Code to create a set of Points and pass them to LineShape

How to do this varies from language to language and, as you might assume, it’s hardest and most dangerous in C++ (because of it’s lack of type safety), slightly easier in Java and PHP (Java because of it’s high type safety and PHP because of it’s lack of any enforced typing).

Variable Length Arguments in C++

To implement in C++ we make use of the va_ functionality provided in stdarg.h. The function is defined as taking the number of parameters passed (int) and then the parameters themselves represented by “…”.

We read the parameter count and then iterate through reading each in turn with va_arg and specifying the type to be used. Note in C++ you must specify the number of parameters being passed when calling the method.

#include <iostream>
#include <stdarg.h>
using namespace std;

// Declare the variable-length argument method
void LineShape(int, ...);

// Our simple Point class
class Point
{
public:
	int x;
	int y;
	Point(int ix, int iy)
	{
		x = ix;
		y = iy;
	}
};

// Definition of LineShape
void LineShape(int n_args, ...)
{
	va_list ap; // arg list
	va_start(ap, n_args); // start on list

	for (int i=1; i<=n_args; i++) // iterate
	{
		// read next argument as Point*
		Point* a = va_arg(ap, Point*);
		cout << a->x << "," << a->y << "\n";
	}
	va_end(ap);
}

int main(int ac, char **av)
{
	Point *a = new Point(10,10);
	Point *b = new Point(15,15);
	Point *c = new Point(10,20);
	LineShape(3, a, b, c);
	return 0;
}

There you have it in C++ (well actually using C libraries); but don’t do it (see above).

Variable Length Arguments in Java

In Java it’s a lot easier as the functionality is built-in to the language. Additionally you don’t need to pass the number of parameters and also the type is determined for the entire set of parameters (in our case Point).

Note that in order for Point to be instantiated as non-static it must be in a seperate file (Point.java).

So our Point class is:

public class Point
{
	public int x;
	public int y;
	Point(int ix, int iy)
	{
		x = ix;
		y = iy;
	}
}

And the main Var.java contains:

public class Var
{
	public static void LineShape(Point... points)
	{
		for (Point p: points)
		{
			System.out.println(p.x + "," + p.y);
		}
	}

	public static void main(String args[])
	{
		Point a = new Point(10,10);
		Point b = new Point(15,15);
		Point c = new Point(10,20);
		LineShape(a,b,c);
	}
}

So in Java we just need to declare a method with Type… name and then iterate through the array in a for loop.

Variable Length Arguments in PHP

PHP isn’t quite as built-in as Java (an actual language construct) but PHP natively provides functions to support variable length parameters to methods such as func_num_args (number of arguments) and func_get_args (arguments as an array).

<?php
class Point
{
	public $x;
	public $y;
	public function Point($ix, $iy)
	{
		$this->x = $ix;
		$this->y = $iy;
	}
}

function LineShape()
{
	$num_args = func_num_args();
	$arg_list = func_get_args();
	for ($i=0; $i < $num_args; $i++)
	{
		$point = $arg_list[$i];
		echo $point->x.",".$point->y."\n";
	}
}

$a = new Point(10,10);
$b = new Point(15,15);
$c = new Point(10,20);

LineShape($a, $b, $c);
?>