Al Zimmermann's contest. page 2

31 posts

Flag Post

For my own benefit, I figured out how to calculate large numbers. So, without further ado, 1000! =

402,387,260,077,093,773,543,702,433,923,003,985,719,374,864,210,714,632,543,799,910,429,938,512,398,629,020,592,044,208,486,969,404,800,479,988,610,197,196,058,631,666,872,994,808,558,901,323,829,669,944,590,997,424,504,087,073,759,918,823,627,727,188,732,519,779,505,950,995,276,120,874,975,462,497,043,601,418,278,094,646,496,291,056,393,887,437,886,487,337,119,181,045,825,783,647,849,977,012,476,632,889,835,955,735,432,513,185,323,958,463,075,557,409,114,262,417,474,349,347,553,428,646,576,611,667,797,396,668,820,291,207,379,143,853,719,588,249,808,126,867,838,374,559,731,746,136,085,379,534,524,221,586,593,201,928,090,878,297,308,431,392,844,403,281,231,558,611,036,976,801,357,304,216,168,747,609,675,871,348,312,025,478,589,320,767,169,132,448,426,236,131,412,508,780,208,000,261,683,151,027,341,827,977,704,784,635,868,170,164,365,024,153,691,398,281,264,810,213,092,761,244,896,359,928,705,114,964,975,419,909,342,221,566,832,572,080,821,333,186,116,811,553,615,836,546,984,046,708,975,602,900,950,537,616,475,847,728,421,889,679,646,244,945,160,765,353,408,198,901,385,442,487,984,959,953,319,101,723,355,556,602,139,450,399,736,280,750,137,837,615,307,127,761,926,849,034,352,625,200,015,888,535,147,331,611,702,103,968,175,921,510,907,788,019,393,178,114,194,545,257,223,865,541,461,062,892,187,960,223,838,971,476,088,506,276,862,967,146,674,697,562,911,234,082,439,208,160,153,780,889,893,964,518,263,243,671,616,762,179,168,909,779,911,903,754,031,274,622,289,988,005,195,444,414,282,012,187,361,745,992,642,956,581,746,628,302,955,570,299,024,324,153,181,617,210,465,832,036,786,906,117,260,158,783,520,751,516,284,225,540,265,170,483,304,226,143,974,286,933,061,690,897,968,482,590,125,458,327,168,226,458,066,526,769,958,652,682,272,807,075,781,391,858,178,889,652,208,164,348,344,825,993,266,043,367,660,176,999,612,831,860,788,386,150,279,465,955,131,156,552,036,093,988,180,612,138,558,600,301,435,694,527,224,206,344,631,797,460,594,682,573,103,790,084,024,432,438,465,657,245,014,402,821,885,252,470,935,190,620,929,023,136,493,273,497,565,513,958,720,559,654,228,749,774,011,413,346,962,715,422,845,862,377,387,538,230,483,865,688,976,461,927,383,814,900,140,767,310,446,640,259,899,490,222,221,765,904,339,901,886,018,566,526,485,061,799,702,356,193,897,017,860,040,811,889,729,918,311,021,171,229,845,901,641,921,068,884,387,121,855,646,124,960,798,722,908,519,296,819,372,388,642,614,839,657,382,291,123,125,024,186,649,353,143,970,137,428,531,926,649,875,337,218,940,694,281,434,118,520,158,014,123,344,828,015,051,399,694,290,153,483,077,644,569,099,073,152,433,278,288,269,864,602,789,864,321,139,083,506,217,095,002,597,389,863,554,277,196,742,822,248,757,586,765,752,344,220,207,573,630,569,498,825,087,968,928,162,753,848,863,396,909,959,826,280,956,121,450,994,871,701,244,516,461,260,379,029,309,120,889,086,942,028,510,640,182,154,399,457,156,805,941,872,748,998,094,254,742,173,582,401,063,677,404,595,741,785,160,829,230,135,358,081,840,096,996,372,524,230,560,855,903,700,624,271,243,416,909,004,153,690,105,933,983,835,777,939,410,970,027,753,472,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

pre in order to avoid massive text wall. Once I ironed out some of the kinks, the calculations all happen very fast (it only took flash 0.13 seconds to calculate that and sew it all into a string).

 
Flag Post

You should get a github repo and upload your code. I’d be interested.

 
Flag Post

For large number calculations like that, it can be convenient to use a programming language like Ruby which natively supports arbitrary-sized integer arithmetic (or some fancy name like that, basically it handles big numbers accurately).

Anyway, the line of ruby code: (1..1000).inject(:*) will give you 1000!

You can try running it here for example.

(The code just means combine all the numbers from 1 to 1000 by multiplying them)

 
Flag Post

Yeah, I could have used a language specifically designed to do it, but setting up everything in order to do it seemed like it would’ve been a bit of a pain.

It’s really quite simple to do, just use an array where each element is a digit in the number. It could probably be optimised quite easily by using a fixed length Vector or a Byte Array? but I was just looking for a quick solution to get it to work. I’ll post it next time I get on Kong.
It reaches its limit at around 10000! (~13 seconds) before it hits the timeout limit of 15, which can probably be circumvented somehow.

 
Flag Post

You can circumvent timeout limits by decomposing the operation into smaller steps and making a small step part of a loop triggered by a Event.EVENT_FRAME, as so:

		private function tick(eve:Event):void
		{
			var deadline:int = getTimer() + updateFrequencyInMs;
			while (getTimer() < deadline)
			{
				if (currentnode)
				{
					walk();
					steps++;
				}
				else
				{
					setupNextSearch();
				}
			}
			updateFields();
		}

To provide a bit of context, that function is part of a program which runs a series of searches by taking steps in a multidimensional space of possible configurations. Like a blind man trekking through a desert searching for an oasis, if you will.

updateFrequencyInMs is the time between two frames (50, at 20 FPS, for instance), so the blind man walks a step, checks his watch, takes another, checks again, and so on, until it’s time to display the next frame or he’s found an oasis (and then the next blind man gets dropped in the desert, or the program ends if it’s out of blind men.) Not only will the program never hit the timeout limit (assuming a single step never takes anywhere close to the timeout limit, in my case I averaged 28-35000 steps per second), but every frame you can update the display to show the user exactly where the program is at, for instance by updating a TextField with the value of a few salient variables. That’s what updateFields() is for, which could just as well have been named reportProgress().

 
Flag Post

That sounds like a very good idea if I ever need complex calculations in games so that people don’t think the game has crashed and leave.

Anyway, here you go. It really is very simple.

public static function bigFact(i:int):String{
	var carry:int,len:int;
	var j:int,k:int;
	var numbers:Array = [1];
	for (j=2;j<i;j++){
		len = numbers.length;
		carry = 0;
		for(k=0;k<len;k++){
			var temp:int = numbers[k]*j + carry;
			if(temp>9)carry = int(temp*0.1);
			else carry = 0;
			numbers[k]= temp - carry*10;
		}
		while(carry!==0){
			numbers[len]=carry - int(carry/10)*10;
			carry/=10;
			len++;
		}
	}
	var number:String = "";
	for(j = numbers.length-1;j>=0;j--){
		number += numbers[j];
		if(j)if(j%3==0)number += ",";
	}
	return number;
}

The digits are held in the array backwards, which allows for easier flexibility and ordering. Every increment of j in the primary loop just multiplies all digits in the array by j, then puts all the carried digits at the end. Passing the final string without commas, or passing the array itself would for all types of further calculations.