...

# 1 != 1

NancyJ
01-04-2008, 05:39 PM
I'm stick in an infinate while loop and I don't know why.

The code is quite simple - while \$number is not prime and is > 1 - keep going - but it gets to one, and keeps going and going and going - I even got it to print out: "\$number is not prime and is > 1" and I got "1 is not prime and is > 1"... wtf? I also tried adding 1 to the prime numbers array but still the same result - it works for everything else, just not for this

while(!(in_array(\$number,\$primes)) )
{

if(\$number % \$primes[\$i]==0)
{
\$number=\$number/\$primes[\$i];
\$factors[\$primes[\$i]]++;
}
else
{
\$i++;
}
}

Actually - 1 should never be the answer anyway - if \$number divided by the next prime_number in the list =1 then \$number is = to the next prime number and is therefore prime and should have dropped out of the loop. The number at the start is 139206 and the prime it seems to get stuck on is 23201 - that should pass the test as being prime and drop it out

Fumigator
01-04-2008, 06:32 PM
If \$number = 1, then your while() condition says if NOT (in_array && \$number NOT 1), which could also be stated if NOT (TRUE && FALSE), which evaulates to TRUE, so it stays in the loop. I think you think the condition says, among other things, while(\$number != 1), but it's not.

NancyJ
01-04-2008, 06:42 PM
23201 and 1 are both in the array - I only put the !=1 in as desperation really, it should stop the loop at 23201

arnyinc
01-04-2008, 07:02 PM
The code has != 1 and your comments refer to > 1. There is a double negative so that solves the mystery about 1 != 1.

I'm a little confused. I'm not sure what the question is after establishing that. It's hard to tell what's going on without being able to run any meaningful test values.

NancyJ
01-04-2008, 07:08 PM
ok, to make this simple, I've taken out anything to do with the 1 - it still doesn't work both 1 and 23201 are in the primes array but it isn't dropping out.

arnyinc
01-04-2008, 07:41 PM
This is completely dependent on data so it's hard to duplicate. When I made a small subset, I had to add a conditional to the while loop:

while(!(in_array(\$number,\$primes)) && \$i<count(\$primes) )

That prevented the if-statement from trying to access the array out of bounds. Not sure if that helps but good luck!

NancyJ
01-04-2008, 09:36 PM
if 23201 wasn't in the array \$primes then \$number would never get to 1. The reason it is 1 is that \$number gets to 23201 then rather than leaving the loop - the loop continues and until it gets to 23201 in the primes array, then it divides \$number by \$primes[\$i] and comes up with 1 (which is also in the primes array and should cause the loop to end)

NancyJ
01-04-2008, 09:37 PM
this is my primenumber function - I use a limit of 50000

the input number is 139206

function esprime(\$limit)
{
\$sqrtlimit = sqrt(\$limit);
\$range = 0;
while(\$range<\$limit){
\$i .= '11';
\$range+=2;
}
\$n = 2;
while(\$n < \$sqrtlimit){
if (\$i[\$n]){
\$sqn = \$n*\$n;
\$k = \$sqn;
\$i[\$k]=0;
while(\$k<=\$limit){
\$k += \$n;
\$i[\$k]=0;
}
}
++\$n;
}
\$n = 1;
while(\$n<\$limit){
if(\$i[\$n]) \$primes[] = \$n;
\$n+=2;
}
if(\$limit>=2) \$primes[0] = 2;
return \$primes;
}

arnyinc
01-04-2008, 10:30 PM
Assuming I understand the goal (which is a stretch), it seems to work. My understanding is that it should break out of the while-loop when \$number gets to 23201 since that is a prime number.

\$primes = esprime(50000);
\$number = 139206;
\$i=0;

while(!(in_array(\$number,\$primes)) )
{
if(\$number % \$primes[\$i]==0)
{
\$number=\$number/\$primes[\$i];
//\$factors[\$primes[\$i]]++;
}
else
{
\$i++;
}
}

echo \$number." is in the array so we broke out" ;

This prints out "23201 is in the array so we broke out".

NancyJ
01-04-2008, 10:45 PM
Assuming I understand the goal (which is a stretch), it seems to work. My understanding is that it should break out of the while-loop when \$number gets to 23201 since that is a prime number.

\$primes = esprime(50000);
\$number = 139206;
\$i=0;

while(!(in_array(\$number,\$primes)) )
{
if(\$number % \$primes[\$i]==0)
{
\$number=\$number/\$primes[\$i];
//\$factors[\$primes[\$i]]++;
}
else
{
\$i++;
}
}

echo \$number." is in the array so we broke out" ;

This prints out "23201 is in the array so we broke out".
windows or linux?

arnyinc
01-04-2008, 10:55 PM
Windows XP and Apache 2.2.

dumpfi
01-04-2008, 10:55 PM
I assume you want to get all prime factors a number consists of. Here is a script that does that:/**
* signature
* array sieve( int, &array )
*
* Computes all primes in the range 0..\$size with the Sieve of Erastothenes and returns an associate array with the primes as keys and 0 as values
*/
function sieve(\$size, &\$flags)
{
\$primes = array();
for(\$i = 2; \$i <= \$size; ++\$i)
{
if(\$flags[\$i])
{
\$primes[\$i] = 0;
for(\$j = \$i<<1; \$j <= \$size; \$j += \$i)
{
\$flags[\$j] = FALSE;
}
}
}
return \$primes;
}

\$number = \$orgNumber = 139206; // number to decompose, \$number will be modified

if(\$number < 1 || (int) (\$number) != \$number) // \$number must be a positive integer
{
exit('error');
}

\$flags = array_fill(0, \$number, TRUE); // an array of boolean flags for the 2nd parameter to sieve()

\$primeMap = sieve(\$number, \$flags); // create a map of all primes in the range of 0..\$number

\$curPrime = key(\$primeMap); // get highest prime

if(isset(\$primeMap[\$number])) // if \$number is a prime itself, we don't need to decompose it
{
++\$primeMap[\$number];
}
elseif(\$number >= 1) // prevent endless loop for \$number < 1
{
do
{
do
{
\$nTemp = (int) (\$number / \$curPrime);
if(\$nTemp * \$curPrime == \$number) // is \$number divisible by \$curPrime without remainder ?
{
\$number = \$nTemp;
++\$primeMap[\$curPrime]; // increase the factor counter for the prime
}
else
{
break; // get a smaller prime for next test
}
}
while(\$number >= \$curPrime); // \$number must be at least >= \$curPrime to be divisible
do
{
prev(\$primeMap); // get the next (lower) prime
\$curPrime = key(\$primeMap);
}
while(\$curPrime > \$number); // \$curPrime must be <= \$number for a division
}
while(\$number != 1); // if \$number == 1 we have all factors
}

// create result string and print it out
\$str = (\$number >= 1) ? '1 * ' : \$number.' * ';
foreach(\$primeMap as \$prime => \$factorCount)
{
if(\$factorCount)
{
\$str .= str_repeat(\$prime.' * ', \$factorCount);
}
}
echo \$orgNumber,' expressed using prime factors: ',substr(\$str, 0, -3);
?>dumpfi

NancyJ
01-04-2008, 11:05 PM
hmm its working now.... of course something else is broken now.
Assuming I understand the goal
Prime factorisation of course!

Ok, so heres the whole story.

I have a number of different factories.Each factory uses a different amount of hours to produce the subcomponents for a given item.
I'm trying to find, how many of each different type of factory I would need to optimise output.

I've tried to solve this problem by:
1. Finding the number of hours required for all the factories to sync up - ie. they all finish at the same time (regardless of how many components they've manufactured ie. factory 1 might have enough components to make 10 items while factory 2 has only made enough for 5) - I'm doing this by calculating the lowest common multiple (lcm) of all the different times involved. I'm finding the lcm using the prime factorisation method - ie. find the prime factors of each number then for each individual prime number in the set of primes you end up with, find the highest number of each of them and then multiply those all together (each prime is multipled by itself the maximum number of times it appears in any 1 number then each of those numbers are multiplied together) and that gives the lcm.

So the lcm tells me how long it would take for all the factories to sync up, then for each factory, I divide the lcm by its time - which tells me how many runs that factory could complete in that time. Then I divide the lcm/max of all the times then divide that by the number of runs for each factory - and thats supposed to always be a whole number... except at the moment, it isnt....

This is the whole code.

function optimalSetup(\$times)
{
\$start = microtime(true);
foreach(\$times as \$key=>\$val)
{
\$times[\$key]=\$val*60;
}
\$lcm = \$this->lcm(\$times);
echo 'lcm is '.\$lcm.'<br />';
\$max = max(\$times);
\$min = min(\$times);
foreach(\$times as \$id => \$time)
{
\$opt[\$id]=(\$lcm/\$min)/(\$lcm/\$time);
}

return \$opt;
}

function lcm(\$numbers)
{
print_r(\$numbers);
\$start = microtime(true);
foreach(\$numbers as \$number)
{
\$primes = \$this->esprime(50000);
\$primes[]=1;
\$pf[\$number] = \$this->primefactors(\$number,\$primes);
foreach(\$pf[\$number] as \$key => \$val)
{
\$primef[\$key][]=pow(\$key,\$val);
}
}

\$total = 1;
foreach(\$primef as \$key => \$val)
{
\$total = \$total * max(\$val);
}

return \$total;
}

function primefactors(\$number,\$primes)
{

\$start = microtime(true);
\$i=0;
if(!is_numeric(\$number))
{
return array();
}
while(!(in_array(\$number,\$primes)) )
{
if(microtime(true)-\$start>2)
{
break;
}
if(\$number%\$primes[\$i]==0)
{
\$number=\$number/\$primes[\$i];
\$factors[\$primes[\$i]]++;
}
else
{
\$i++;
}
}
\$factors[\$number]++;
return \$factors;
}

function esprime(\$limit)
{
\$sqrtlimit = sqrt(\$limit);
\$range = 0;
while(\$range<\$limit){
\$i .= '11';
\$range+=2;
}
\$n = 2;
while(\$n < \$sqrtlimit){
if (\$i[\$n]){
\$sqn = \$n*\$n;
\$k = \$sqn;
\$i[\$k]=0;
while(\$k<=\$limit){
\$k += \$n;
\$i[\$k]=0;
}
}
++\$n;
}
\$n = 1;
while(\$n<\$limit){
if(\$i[\$n]) \$primes[] = \$n;
\$n+=2;
}
if(\$limit>=2) \$primes[0] = 2;
return \$primes;
}
}

This is the current example I'm working on

* 600 minutes @ Forge
* 360 minutes @ Logging Camp (Fir)
* 3000 minutes @ Mine (Iron)
* 720 minutes @ Mine (Sulfur)
* 600 minutes @ Plantation (General)
* 450 minutes @ Powder Mill
* 6000 minutes @ Quarry (Limestone)
* 1080 minutes @ Saltpeter Caves
* 240 minutes @ Tar Distillery
* 60 minutes @ Textile Mill
* 342 minutes @ Weaponsmith

this tells me I need

* 5.7 x Weaponsmith
* 7.5 x Powder Mill
* 6 x Logging Camp (Fir)
* 18 x Saltpeter Caves
* 12 x Mine (Sulfur)
* 10 x Forge
* 100 x Quarry (Limestone)
* 50 x Mine (Iron)
* 1 x Textile Mill
* 10 x Plantation (General)
* 4 x Tar Distillery

but it should always be a whole number and I don't know whether its my logic or my code

dumpfi
01-04-2008, 11:36 PM
You must compute the lcm for the subcomponents, too. Here's an example:<?php
function gcd(\$a, \$b) // greatest common denominator
{
while(\$b)
{
\$t = \$b;
\$b = \$a % \$b;
\$a = \$t;
}
return \$a;
}
function lcm(\$a, \$b) // least common multiple -> much easier and faster to compute with gcd than with prime factorisation!
{
return \$a * \$b / gcd(\$a, \$b);
}

\$times = array( // our data
'Forge' => 600,
'Logging Camp (Fir)' => 360,
'Mine (Iron)' => 3000,
'Mine (Sulfur)' => 720,
'Plantation (General)' => 600,
'Powder Mill' => 450,
'Quarry (Limestone)' => 6000,
'Saltpeter Caves' => 1080,
'Tar Distillery' => 240,
'Textile Mill' => 60,
'Weaponsmith' => 342);

\$syncTime = array_reduce(\$times, 'lcm', 1); // get the sync time, when all factories have finished producing a sub component

\$components = array();

foreach(\$times as \$factory => \$time) // compute for each factory how many sub components it has produced at the sync time
{
\$components[\$factory] = \$syncTime / \$time;
}

\$syncComponents = array_reduce(\$components, 'lcm', 1); // when will all factories have produced the same amount of sub comonents ?

foreach(\$components as \$factory => \$parts) // compute the needed number of factories and display it
{
echo \$syncComponents / \$parts,' ',\$factory,' needed<br>';
}
?>Output:100 Forge needed
60 Logging Camp (Fir) needed
500 Mine (Iron) needed
120 Mine (Sulfur) needed
100 Plantation (General) needed
75 Powder Mill needed
1000 Quarry (Limestone) needed
180 Saltpeter Caves needed
40 Tar Distillery needed
10 Textile Mill needed
57 Weaponsmith neededdumpfi

NancyJ
01-05-2008, 10:31 PM
I tried that and on one of the recipes I'm looking at, its come up with negtive numbers - now thats impressive.

* 6 hours 12 minutes @ Carpenter
* 42 minutes @ Curing Shed
* 8 hours @ Fishing Lodge
* 49 hours 36 minutes @ Forge
* 42 hours @ Grain Mill
* 2 hours @ Hunting Lodge
* 12 hours 24 minutes @ Logging Camp (Oak)
* 248 hours @ Mine (Iron)
* 844 hours 48 minutes @ Plantation (General)
* 272 hours @ Plantation (Sugar)
* 7 hours @ Provisioner
* 496 hours @ Quarry (Limestone)
* 2 hours @ Rum Distillery
* 6 hours 48 minutes @ Sugar Refinery
* 96 hours @ Vineyard
* 1 hour 48 minutes @ Winery

* -7.51649237213E+013 x Provisioner
* -9.07133250853E+015 x Plantation (General)
* -7.51649237213E+012 x Curing Shed
* -8.59027699671E+013 x Fishing Lodge
* -4.50989542328E+014 x Grain Mill
* -2.14756924918E+013 x Hunting Lodge
* -2.14756924918E+013 x Rum Distillery
* -6.65746467245E+013 x Carpenter
* -5.32597173796E+014 x Forge
* -5.32597173796E+015 x Quarry (Limestone)
* -2.66298586898E+015 x Mine (Iron)
* -1.33149293449E+014 x Logging Camp (Oak)
* -7.30173544721E+013 x Sugar Refinery
* -2.92069417888E+015 x Plantation (Sugar)
* -1.93281232426E+013 x Winery
* -1.03083323961E+015 x Vineyard

dumpfi
01-06-2008, 12:02 PM
The negative numbers are due to integer overflow. You can fix this by using GMP (http://www.php.net/manual/en/function.gmp-gcd.php) or BCMath functions (http://www.php.net/manual/en/ref.bc.php):<?php
function lcm(\$a, \$b) // least common multiple -> much easier and faster to compute with gcd than with prime factorisation!
{
return gmp_div(gmp_mul(\$a, \$b), gmp_gcd(\$a, \$b));
}

\$times = array( // our data
'Carpenter' => 372,
'Curing Shed' => 42,
'Fishing Lodge' => 480,
'Forge' => 2976,
'Grain Mill' => 2520,
'Hunting Lodge' => 120,
'Logging Camp (Oak)' => 744,
'Mine (Iron)' => 14880,
'Plantation (General)' => 50688,
'Plantation (Sugar)' => 16320,
'Provisioner' => 420,
'Quarry (Limestone)' => 29760,
'Rum Distillery' => 120,
'Sugar Refinery' => 408,
'Vineyard' => 5760,
'Winery' => 108);

\$syncTime = array_reduce(\$times, 'lcm', 1); // get the sync time, when all factories have finished producing a sub component

\$components = array();

foreach(\$times as \$factory => \$time) // compute for each factory how many sub components it has produced at the sync time
{
\$components[\$factory] = gmp_div(\$syncTime, \$time);
}

\$syncComponents = array_reduce(\$components, 'lcm', 1); // when will all factories have produced the same amount of sub comonents ?

foreach(\$components as \$factory => \$parts) // compute the needed number of factories and display it
{
echo gmp_strval(gmp_div(\$syncComponents, \$parts)),' ',\$factory,' needed<br>';
}
?>dumpfi

NancyJ
01-06-2008, 05:07 PM
I fixed the negatives with a little rounding up of some of the times but its still not right - I thought I had it sorted, so I put it live but now I'm finding loads that aren't right - not whole numbers....

http://potbs.simstressgames.com/materials/show/92
http://potbs.simstressgames.com/materials/show/154

...maybe I should just give up :(

oh and I tried the gmp functions and it failed spectacularly - tons of 'wrong type' errors.

dumpfi
01-06-2008, 06:12 PM
The GMP functions only work with integers and integer strings. That's why you must cast any floating point number to integer before you pass it to them.

If you must calculate with floating point numbers, use the BCMath functions, as they aren't integer-only.

dumpfi

abduraooft
01-08-2008, 07:59 AM
if(\$number % \$primes[\$i]==0)
I've been getting the mod operator (%) in its equivalent & #37;form through out this thread. Is it for me only?

matak
01-08-2008, 12:24 PM
I've been getting the mod operator (%) in its equivalent & #37;form through out this thread. Is it for me only?

no, that is normal when using php tags with vbulletin