Thread: Fasten up a programme with large numbers

If you want to get larger integers then it might be worth looking for a library. Otherwise, you could write your own, but that would take longer and you would have to check it worked as it was suppose to before you could even use it.

There are plenty of possibilities through google for large integer calculation libraries.

In terms of reducing the running time of your program (although you said you wanted to reduce the compile-time of the code, I presume you are actually talking about the running time), you may have to try implementing a less computationally intensive algorithm from the outset.

At the moment your algorithm isn't such a problem for small integers, but for large integers you are going to have problems because of the double loop. One idea is that instead of going through each i and j combination, once you find a value of i which is a factor of j, then simply sum it with all it's multiples at the same time.

E.g. 28 is a perfect number, and 28 can be written as a sum of its factors as so:
28 = 1 + 2 + 4 + 7 + 14.
I.e. Once you know that 14 is a factor of 28, you automatically know that 7 is too. Likewise applies for 4 and 2. But remember, knowing that 2 is a factor of a number doesn't necessarily mean that 4 is. For this reason, when you are searching for factors start at the number and work down.

In the above example, once you have worked out that 14 is a factor you can automatically add 7 to the sum and then ignore the '7' when you find it as a factor. This is a fairly simple example, and I don't know how much it will increase the running speed of your code, but I think it should help a bit.

Edit:
Taking another example: 496. The factors are: 1, 2, 4, 8, 16, 31, 62, 124, 248
But if you find 248 is a factor then you can speed up your summation by then realising that 124 is a factor of 248 and hence 496. And then realise that 62 is a factor of 124, hence 248 and 496 etc.
This means that instead of testing the numbers one by one, once you find one you then gain access to a whole series of factors. You can obviously add these to your summation and then ignore these numbers when you get to them later in your loop. Reducing the number of comparisons/calculations which need to be done.

1) Tt is the running time you're concerned about. I am sure it compiles very very very fast.
2) You can speed it up by noticing that no odd perfect numbers have yet been discovered. Certainly you can skip odd numbers for a factor of two improvement.
3) In your approach, you could just go to one half of j, since a number greater than j/2 cannot possibly be a factor. (Eg, clearly 9 is the greatest proper divisor of 18, so why bother with 10, 11, 12, etc?)
4) I'd look into factorization algorithm that's more sophisticated than just checking every possible number less than n. Suppose you could could factor a number into its prime factors. Then you could easily skip a lot of numbers that cannot possibly be factors. Consider a number like 360. Well, 360=2^3 * 3^2 * 5^1. Therefore any multiple of 7 will not divide it and so on.

EDIT: In fact ya, just factor each of the numbers and then add up the factors and see if they sum to n. If a number k can be factored into k=m^x * n^y * o^z... then all you have to do is create an array containing all the possible combinations of the prime factors.

Taking as an example k=24, we have k = 24 = 2^3 * 3^1. (In the notation above, m=2, n=3, x=3, y=1). Then the factors are 1,2,3,4,6,8,12,24 which correspond to all the combinations where 0 <= x <= 3 and 0 <= y <= 1:
1 = 2^0*3^0
2 = 2^1 * 3^0
3 = 2^0 * 3^1
4 = 2^2 * 3^0
6 = 2^1 * 3^1
8 = 2^3 * 3^0
12 = 2^2 * 3^1
24 = 2^3 * 3^1

Hold on, I am working on a C++ implementation of a naive prime factorization for fun. I'll post it when I refine it (about 10 minutes)

EDIT: I know this is C++ code and technically shouldn't go here, but it's just a demonstration that one could factorize the numbers. I also brain-farted, so I can't think of how to actually pick out each proper divisor. I know that we have to try all the combinations of the prime factors. I just can't think of the code right now.

Code:

#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

// Because this is naive, we will just recursively put prime factors in a "bucket"
// This algorithm has the advantage that it's what most of us actually do when WE
// sit down to factorize a number.
void Factorize(int n, map<int, int>& factor_list)
{
	map<int,int>::iterator it;

	for(int i = 2; i <= n; i++)
	{
		if(n % i == 0)
		{
			// Check if i has been found to be a prime factor yet
			it = factor_list.find(i);
			if(it == factor_list.end()) // First time we have found this prime factor
			{
				factor_list.insert( pair<int, int>(i, 1) );
			}
			else // We just have to increment the power of this prime factor
			{
				it->second++;
			}
			Factorize(n / i, factor_list); // Factor the smaller result
			return;
		}
	}
}

int main(int argc, char** argv)
{
	if(argc < 2)
	{
		cout << "Usage: ./foo [NUMBER]" << endl;
		return 0;
	}

	map<int, int> factor_list;

	Factorize(std::atoi(argv[1]), factor_list);
	// Print out the factorization
	for(map<int,int>::const_iterator it = factor_list.begin(); it != factor_list.end(); ++it)
	{
		cout << it->first << "^" << it->second << endl;
	}
	return 0;
}

While we're at it, here's some irrelevant C# code I just whipped up to find the perfect numbers in 2 < n < 100000:

Code:

using System;
using System.Collections.Generic;

namespace PerfectNumbers
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 2; i < 100000; ++i)
                if (i.IsPerfect())
                    Console.Write("{0} ", i);
            Console.Write('\n');
        }
    }

    public static class MyExtensions
    {
        public static IEnumerable<int> Factors(this int num)
        {
            List<int> factors = new List<int>();

            for (int i = 1; i <= num / 2; ++i)
                if (num % i == 0)
                    factors.Add(i);

            return factors;
        }

        public static bool IsPerfect(this int num)
        {
            return num.Factors().Sum() == num;
        }
    }
}

itsme86: Yes, hahahaha. Well at least your snipe taught me something about GLib. I learned that GLib is annoying:

Code:

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

// Because this is naive, we will just recursively put prime factors in a "bucket"
// This algorithm has the advantage that it's what most of us actually do when WE
// sit down to factorize a number.
void Factorize(int n, GHashTable* factor_list)
{
	int i;
	for(i = 2; i <= n; i++)
	{
		if(n % i == 0)
		{
			// Check if i has been found to be a prime factor yet
			gpointer it = g_hash_table_lookup(factor_list, &i);
			if(it == NULL) // First time we have found this prime factor
			{
				int* k = malloc(sizeof(int)); *k = i;
				int* v = malloc(sizeof(int)); *v = 1;
				g_hash_table_insert(factor_list, k, v);
			}
			else // We just have to increment the power of this prime factor
			{
				(*(int*)it)++;
			}
			Factorize(n / i, factor_list); // Factor the smaller result
			return;
		}
	}
}

void Print(gpointer key, gpointer value, gpointer user_data)
{
	printf("%d^%d\n", *(int*)key, *(int*)value);
}

int main(int argc, char** argv)
{
	if(argc < 2)
	{
		printf("Usage: ./foo [NUMBER]\n");
		return 0;
	}

	GHashTable* factor_list = g_hash_table_new_full( g_int_hash, g_int_equal, FreeElement, FreeElement );

	Factorize(atoi(argv[1]), factor_list);
	g_hash_table_foreach(factor_list, Print, NULL);
	g_hash_table_destroy(factor_list);
	return 0;
}