|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
On September 01 2012 03:54 waxypants wrote:Show nested quote +On September 01 2012 03:50 LukeNukeEm wrote:Hi guys, I have a question regarding multithreading in c++. Currently I have a number of threads (say 5), and a number of jobs (say 100). Right now, Thread 1 solves jobs 0, 5, 10, ..., Thread 2 solves jobs 1, 6, 11, ... etc. However this sucks if the jobs take a different amount of time. What i would like to do is have some sort of simple function/method that the threads can call and get a jobnumber, similar to this: int getJobNumber()
{
static unsigned int jobNumber = 0;
return jobNumber++;
} - only that it has to be safe for multithreaded use. Any pointers to what i should look into? Thanks Use a mutex.
Thank you very much 
|
On September 01 2012 03:59 LukeNukeEm wrote:Show nested quote +On September 01 2012 03:54 waxypants wrote:On September 01 2012 03:50 LukeNukeEm wrote:Hi guys, I have a question regarding multithreading in c++. Currently I have a number of threads (say 5), and a number of jobs (say 100). Right now, Thread 1 solves jobs 0, 5, 10, ..., Thread 2 solves jobs 1, 6, 11, ... etc. However this sucks if the jobs take a different amount of time. What i would like to do is have some sort of simple function/method that the threads can call and get a jobnumber, similar to this: int getJobNumber()
{
static unsigned int jobNumber = 0;
return jobNumber++;
} - only that it has to be safe for multithreaded use. Any pointers to what i should look into? Thanks Use a mutex. Thank you very much
If you're on windows, these may be interesting to you:
InterlockedIncrement: http://msdn.microsoft.com/en-us/library/windows/desktop/ms683614(v=vs.85).aspx
Synchronization Primitives: http://msdn.microsoft.com/en-us/library/windows/desktop/ms686360(v=vs.85).aspx
|
On September 01 2012 04:04 cowsrule wrote:Show nested quote +On September 01 2012 03:59 LukeNukeEm wrote:On September 01 2012 03:54 waxypants wrote:On September 01 2012 03:50 LukeNukeEm wrote:Hi guys, I have a question regarding multithreading in c++. Currently I have a number of threads (say 5), and a number of jobs (say 100). Right now, Thread 1 solves jobs 0, 5, 10, ..., Thread 2 solves jobs 1, 6, 11, ... etc. However this sucks if the jobs take a different amount of time. What i would like to do is have some sort of simple function/method that the threads can call and get a jobnumber, similar to this: int getJobNumber()
{
static unsigned int jobNumber = 0;
return jobNumber++;
} - only that it has to be safe for multithreaded use. Any pointers to what i should look into? Thanks Use a mutex. Thank you very much If you're on windows, these may be interesting to you: InterlockedIncrement: http://msdn.microsoft.com/en-us/library/windows/desktop/ms683614(v=vs.85).aspxSynchronization Primitives: http://msdn.microsoft.com/en-us/library/windows/desktop/ms686360(v=vs.85).aspx
Are there any advantages i would gain using InterlockedIncrement over a Mutex?
|
On September 01 2012 04:14 LukeNukeEm wrote:Show nested quote +On September 01 2012 04:04 cowsrule wrote:On September 01 2012 03:59 LukeNukeEm wrote:On September 01 2012 03:54 waxypants wrote:On September 01 2012 03:50 LukeNukeEm wrote:Hi guys, I have a question regarding multithreading in c++. Currently I have a number of threads (say 5), and a number of jobs (say 100). Right now, Thread 1 solves jobs 0, 5, 10, ..., Thread 2 solves jobs 1, 6, 11, ... etc. However this sucks if the jobs take a different amount of time. What i would like to do is have some sort of simple function/method that the threads can call and get a jobnumber, similar to this: int getJobNumber()
{
static unsigned int jobNumber = 0;
return jobNumber++;
} - only that it has to be safe for multithreaded use. Any pointers to what i should look into? Thanks Use a mutex. Thank you very much If you're on windows, these may be interesting to you: InterlockedIncrement: http://msdn.microsoft.com/en-us/library/windows/desktop/ms683614(v=vs.85).aspxSynchronization Primitives: http://msdn.microsoft.com/en-us/library/windows/desktop/ms686360(v=vs.85).aspx Are there any advantages i would gain using InterlockedIncrement over a Mutex?
In this case, InterlockedIncrement is simpler. I think you can just do something like:
unsigned int getJobNumber()
{
static unsigned int jobNumber = 0;
return InterlockedIncrement(&jobNumber) - 1;
}
note: might have to change types or cast or something if it doesn't like that
|
On September 01 2012 05:43 waxypants wrote:Show nested quote +On September 01 2012 04:14 LukeNukeEm wrote:On September 01 2012 04:04 cowsrule wrote:On September 01 2012 03:59 LukeNukeEm wrote:On September 01 2012 03:54 waxypants wrote:On September 01 2012 03:50 LukeNukeEm wrote:Hi guys, I have a question regarding multithreading in c++. Currently I have a number of threads (say 5), and a number of jobs (say 100). Right now, Thread 1 solves jobs 0, 5, 10, ..., Thread 2 solves jobs 1, 6, 11, ... etc. However this sucks if the jobs take a different amount of time. What i would like to do is have some sort of simple function/method that the threads can call and get a jobnumber, similar to this: int getJobNumber()
{
static unsigned int jobNumber = 0;
return jobNumber++;
} - only that it has to be safe for multithreaded use. Any pointers to what i should look into? Thanks Use a mutex. Thank you very much If you're on windows, these may be interesting to you: InterlockedIncrement: http://msdn.microsoft.com/en-us/library/windows/desktop/ms683614(v=vs.85).aspxSynchronization Primitives: http://msdn.microsoft.com/en-us/library/windows/desktop/ms686360(v=vs.85).aspx Are there any advantages i would gain using InterlockedIncrement over a Mutex? In this case, InterlockedIncrement is simpler. I think you can just do something like:
unsigned int getJobNumber()
{
static unsigned int jobNumber = 0;
return InterlockedIncrement(&jobNumber) - 1;
}
note: might have to change types or cast or something if it doesn't like that
i think i'll stick with the mutex, seems easier to change something inside the "locked" section.
|
On August 31 2012 19:40 spudde123 wrote:@frogmelter I think I you misunderstood my post (or I was too unclear). I said that you start with an empty list L. So you have a list 22335577 which we shall call P. Step 1. Add 2 to L because L is empty. Step 2. Multiply 2*2 and add 4 to L, 2 is already there Step 3. Multiply 2*3 and 4*3 and add 6 and 12 into L, add also 3 into L. etc. So as you move in P from left to right in each iteration you multiply all the products of all possible subsets of numbers left from the current position. This way you will get all the factors. (Not saying it is the best or even a good way) edit: For illustration here is the necessary code in R to produce the factors of your example. I just quickly tested it using R so I don't have to bother coding checks whether a number is already in the list.
P <- c(2,2,3,3,5,5,7,7)
L <- c(1)
for(i in 1:length(P))
{
tmp <- L*P[i]
L <- c(L,tmp)
L <- unique(L)
}
#Print length of L
length(L)
#Print L
sort(L)
Using this the output is the following: + Show Spoiler +
> length(L)
[1] 81
> sort(L)
[1] 1 2 3 4 5 6 7 9 10 12 14 15
[13] 18 20 21 25 28 30 35 36 42 45 49 50
[25] 60 63 70 75 84 90 98 100 105 126 140 147
[37] 150 175 180 196 210 225 245 252 294 300 315 350
[49] 420 441 450 490 525 588 630 700 735 882 900 980
[61] 1050 1225 1260 1470 1575 1764 2100 2205 2450 2940 3150 3675
[73] 4410 4900 6300 7350 8820 11025 14700 22050 44100
Big thank you to you sir
On September 01 2012 03:48 waxypants wrote:Show nested quote +On September 01 2012 03:23 waxypants wrote:On August 31 2012 12:56 frogmelter wrote:On August 30 2012 17:48 spudde123 wrote:
I didn't spend too much time thinking whether the following is the best way of producing all the possible products but at least consider it food for thought!
Let's say you have a prime factorization, each prime with some exponent. Now consider that you drop the exponents and instead have a list of prime factors and the number of times a prime is in the list is based on the exponent.
So if you have a prime factorization 2^2 * 3^2 * 5^2 * 7^2 consider it as a list 22335577.
Now if you want to list the products of each different subset of this list you can do the following:
Start with an empty list L
For each member N in the list of primes
Multiply each member of L with N and add the new numbers you get to L if they are not already there
add N to L if it is not already there
end
And in the end L will include all the divisors of your original number (other than 1)
Now obviously you don't need to produce this list but instead if you have the primes and their exponents you can just loop for each separate prime from 1 to the exponent to achieve the same goal but I thought this was more illustrative.
I'm not sure this will work without some serious reworking [unless I'm dumb and misunderstood] Let's say step one you have 2 2 3 3 5 5 7 7 If I start with 2 and multiply everything by it, the result is this [assuming I take it out from the list afterwards] 4 6 6 10 10 14 14 Now it starts to get tricky. 4 can not be multiplied by 2 again since it will yield 8, which is not one of the factors. However, everything else can be multiplied by 2 to get more factors Basically, in a nutshell, there are certain parts of each list that can not be re-mulitplied. This would require each number to be an object and to store everything that was multiplied to get that number. Not sure if it's the best solution. On August 31 2012 05:24 waxypants wrote:On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Yes it is a recursion. Here is a python solution. I didn't completely test but the results look about right at a glance).
def factors_from_prime_factors(prime_factors):
if not prime_factors:
return []
else:
factors = factors_from_prime_factors(prime_factors[1:]
factors = prime_factors + map(lambda x: x*prime_factors[0], factors)
factors = list(set(factors))
factors.sort()
return factors
The prime factors must be given as a list like [2, 2, 3, 3, 5, 5, 7, 7] in the 44100 case. >>> factors_from_prime_factors([2, 2, 3, 3, 5, 5, 7, 7]) [2, 3, 4, 5, 6, 7, 10, 12, 14, 20, 28, 36, 60, 84, 180, 252, 900, 1260, 6300, 44100] edit: sorting can be taken out or done outside the function, same with the conversion to a set (it just removes duplicates), but I just put them in one function for simplicity and to look nice Hmmm... Looks like you might be missing a few there. http://www.wolframalpha.com/input/?i=factors of 44100This tells me that there are 81 divisors for it, including 22050 [exactly half of it] which I don't see on your list I have an idea for what I need to do. I just gotta code it. On August 31 2012 05:34 zzdd wrote:On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Google Miller Rabin. It will take you maybe an hour to do and is way simpler. Well, looking at Miller Rabin, it seems to be a test to figure out whether a number is prime or not. My assignment is to find all the factors of a large number and list the ones that are prime. I'm not sure how Miller Rabin would help me there, since I already have all the prime factors. You're right, oops. Guess checking for 22050 should have been obvious before I posted it Hmm now I'm going to have to go back and figure out where I went wrong. Ahh was missing one little part. Seems ok now. I know you probably don't need this, but just posting for my own satisfaction
def factors_from_prime_factors(prime_factors):
if not prime_factors:
return []
else:
factors = factors_from_prime_factors(prime_factors[1:])
factors = prime_factors + factors + map(lambda x: x*prime_factors[0], factors)
factors = list(set(factors))
factors.sort()
return factors
>>> factors = factors_from_prime_factors([2, 2, 3, 3, 5, 5, 7, 7]) >>> print factors [2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 25, 28, 30, 35, 36, 42, 45, 49, 50, 60, 63, 70, 75 , 84, 90, 98, 100, 105, 126, 140, 147, 150, 175, 180, 196, 210, 225, 245, 252, 294, 300, 315, 350, 4 20, 441, 450, 490, 525, 588, 630, 700, 735, 882, 900, 980, 1050, 1225, 1260, 1470, 1575, 1764, 2100, 2205, 2450, 2940, 3150, 3675, 4410, 4900, 6300, 7350, 8820, 11025, 14700, 22050, 44100] >>> len(factors) 80
Big thank you to you as well.
I will rewrite both methods and compare runtimes to see which one is better.
|
On September 01 2012 13:38 frogmelter wrote:Show nested quote +On August 31 2012 19:40 spudde123 wrote:@frogmelter I think I you misunderstood my post (or I was too unclear). I said that you start with an empty list L. So you have a list 22335577 which we shall call P. Step 1. Add 2 to L because L is empty. Step 2. Multiply 2*2 and add 4 to L, 2 is already there Step 3. Multiply 2*3 and 4*3 and add 6 and 12 into L, add also 3 into L. etc. So as you move in P from left to right in each iteration you multiply all the products of all possible subsets of numbers left from the current position. This way you will get all the factors. (Not saying it is the best or even a good way) edit: For illustration here is the necessary code in R to produce the factors of your example. I just quickly tested it using R so I don't have to bother coding checks whether a number is already in the list.
P <- c(2,2,3,3,5,5,7,7)
L <- c(1)
for(i in 1:length(P))
{
tmp <- L*P[i]
L <- c(L,tmp)
L <- unique(L)
}
#Print length of L
length(L)
#Print L
sort(L)
Using this the output is the following: + Show Spoiler +
> length(L)
[1] 81
> sort(L)
[1] 1 2 3 4 5 6 7 9 10 12 14 15
[13] 18 20 21 25 28 30 35 36 42 45 49 50
[25] 60 63 70 75 84 90 98 100 105 126 140 147
[37] 150 175 180 196 210 225 245 252 294 300 315 350
[49] 420 441 450 490 525 588 630 700 735 882 900 980
[61] 1050 1225 1260 1470 1575 1764 2100 2205 2450 2940 3150 3675
[73] 4410 4900 6300 7350 8820 11025 14700 22050 44100
Big thank you to you sir Show nested quote +On September 01 2012 03:48 waxypants wrote:On September 01 2012 03:23 waxypants wrote:On August 31 2012 12:56 frogmelter wrote:On August 30 2012 17:48 spudde123 wrote:
I didn't spend too much time thinking whether the following is the best way of producing all the possible products but at least consider it food for thought!
Let's say you have a prime factorization, each prime with some exponent. Now consider that you drop the exponents and instead have a list of prime factors and the number of times a prime is in the list is based on the exponent.
So if you have a prime factorization 2^2 * 3^2 * 5^2 * 7^2 consider it as a list 22335577.
Now if you want to list the products of each different subset of this list you can do the following:
Start with an empty list L
For each member N in the list of primes
Multiply each member of L with N and add the new numbers you get to L if they are not already there
add N to L if it is not already there
end
And in the end L will include all the divisors of your original number (other than 1)
Now obviously you don't need to produce this list but instead if you have the primes and their exponents you can just loop for each separate prime from 1 to the exponent to achieve the same goal but I thought this was more illustrative.
I'm not sure this will work without some serious reworking [unless I'm dumb and misunderstood] Let's say step one you have 2 2 3 3 5 5 7 7 If I start with 2 and multiply everything by it, the result is this [assuming I take it out from the list afterwards] 4 6 6 10 10 14 14 Now it starts to get tricky. 4 can not be multiplied by 2 again since it will yield 8, which is not one of the factors. However, everything else can be multiplied by 2 to get more factors Basically, in a nutshell, there are certain parts of each list that can not be re-mulitplied. This would require each number to be an object and to store everything that was multiplied to get that number. Not sure if it's the best solution. On August 31 2012 05:24 waxypants wrote:On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Yes it is a recursion. Here is a python solution. I didn't completely test but the results look about right at a glance).
def factors_from_prime_factors(prime_factors):
if not prime_factors:
return []
else:
factors = factors_from_prime_factors(prime_factors[1:]
factors = prime_factors + map(lambda x: x*prime_factors[0], factors)
factors = list(set(factors))
factors.sort()
return factors
The prime factors must be given as a list like [2, 2, 3, 3, 5, 5, 7, 7] in the 44100 case. >>> factors_from_prime_factors([2, 2, 3, 3, 5, 5, 7, 7]) [2, 3, 4, 5, 6, 7, 10, 12, 14, 20, 28, 36, 60, 84, 180, 252, 900, 1260, 6300, 44100] edit: sorting can be taken out or done outside the function, same with the conversion to a set (it just removes duplicates), but I just put them in one function for simplicity and to look nice Hmmm... Looks like you might be missing a few there. http://www.wolframalpha.com/input/?i=factors of 44100This tells me that there are 81 divisors for it, including 22050 [exactly half of it] which I don't see on your list I have an idea for what I need to do. I just gotta code it. On August 31 2012 05:34 zzdd wrote:On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Google Miller Rabin. It will take you maybe an hour to do and is way simpler. Well, looking at Miller Rabin, it seems to be a test to figure out whether a number is prime or not. My assignment is to find all the factors of a large number and list the ones that are prime. I'm not sure how Miller Rabin would help me there, since I already have all the prime factors. You're right, oops. Guess checking for 22050 should have been obvious before I posted it Hmm now I'm going to have to go back and figure out where I went wrong. Ahh was missing one little part. Seems ok now. I know you probably don't need this, but just posting for my own satisfaction
def factors_from_prime_factors(prime_factors):
if not prime_factors:
return []
else:
factors = factors_from_prime_factors(prime_factors[1:])
factors = prime_factors + factors + map(lambda x: x*prime_factors[0], factors)
factors = list(set(factors))
factors.sort()
return factors
>>> factors = factors_from_prime_factors([2, 2, 3, 3, 5, 5, 7, 7]) >>> print factors [2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 25, 28, 30, 35, 36, 42, 45, 49, 50, 60, 63, 70, 75 , 84, 90, 98, 100, 105, 126, 140, 147, 150, 175, 180, 196, 210, 225, 245, 252, 294, 300, 315, 350, 4 20, 441, 450, 490, 525, 588, 630, 700, 735, 882, 900, 980, 1050, 1225, 1260, 1470, 1575, 1764, 2100, 2205, 2450, 2940, 3150, 3675, 4410, 4900, 6300, 7350, 8820, 11025, 14700, 22050, 44100] >>> len(factors) 80 Big thank you to you as well. I will rewrite both methods and compare runtimes to see which one is better.
pseudo ruby, not the fastest, but damn simple
def factor(n)
for i in 1...sqrt n
if n % i == 0
yield i
yield n / i
def factors_from_prime_factors(pf)
num = pf.reduce 1, { |prod, n| prod * n}
factor(num) { |n| puts n }
If you have to determine prime factors for very large numbers, use Fermat's Probable Prime method; checking against a table of precomputed Carmichael numbers.
|
PROGRAMMING CHALLENGE:
Write a program that solves a cryptogram puzzle.
+ Your program may not rely on human hints, feedback.
+ You may use as large of a dictionary or training data as you want.
+ You may use randomized algorithms, but your program should expectedly generate all possible solutions.
+ Assume all words belong to simple English (no proper nouns) and a lower-cased alphabet of a-z, with punctuation stripped.
|
On September 01 2012 13:38 frogmelter wrote:Show nested quote +On August 31 2012 19:40 spudde123 wrote:@frogmelter I think I you misunderstood my post (or I was too unclear). I said that you start with an empty list L. So you have a list 22335577 which we shall call P. Step 1. Add 2 to L because L is empty. Step 2. Multiply 2*2 and add 4 to L, 2 is already there Step 3. Multiply 2*3 and 4*3 and add 6 and 12 into L, add also 3 into L. etc. So as you move in P from left to right in each iteration you multiply all the products of all possible subsets of numbers left from the current position. This way you will get all the factors. (Not saying it is the best or even a good way) edit: For illustration here is the necessary code in R to produce the factors of your example. I just quickly tested it using R so I don't have to bother coding checks whether a number is already in the list.
P <- c(2,2,3,3,5,5,7,7)
L <- c(1)
for(i in 1:length(P))
{
tmp <- L*P[i]
L <- c(L,tmp)
L <- unique(L)
}
#Print length of L
length(L)
#Print L
sort(L)
Using this the output is the following: + Show Spoiler +
> length(L)
[1] 81
> sort(L)
[1] 1 2 3 4 5 6 7 9 10 12 14 15
[13] 18 20 21 25 28 30 35 36 42 45 49 50
[25] 60 63 70 75 84 90 98 100 105 126 140 147
[37] 150 175 180 196 210 225 245 252 294 300 315 350
[49] 420 441 450 490 525 588 630 700 735 882 900 980
[61] 1050 1225 1260 1470 1575 1764 2100 2205 2450 2940 3150 3675
[73] 4410 4900 6300 7350 8820 11025 14700 22050 44100
Big thank you to you sir Show nested quote +On September 01 2012 03:48 waxypants wrote:On September 01 2012 03:23 waxypants wrote:On August 31 2012 12:56 frogmelter wrote:On August 30 2012 17:48 spudde123 wrote:
I didn't spend too much time thinking whether the following is the best way of producing all the possible products but at least consider it food for thought!
Let's say you have a prime factorization, each prime with some exponent. Now consider that you drop the exponents and instead have a list of prime factors and the number of times a prime is in the list is based on the exponent.
So if you have a prime factorization 2^2 * 3^2 * 5^2 * 7^2 consider it as a list 22335577.
Now if you want to list the products of each different subset of this list you can do the following:
Start with an empty list L
For each member N in the list of primes
Multiply each member of L with N and add the new numbers you get to L if they are not already there
add N to L if it is not already there
end
And in the end L will include all the divisors of your original number (other than 1)
Now obviously you don't need to produce this list but instead if you have the primes and their exponents you can just loop for each separate prime from 1 to the exponent to achieve the same goal but I thought this was more illustrative.
I'm not sure this will work without some serious reworking [unless I'm dumb and misunderstood] Let's say step one you have 2 2 3 3 5 5 7 7 If I start with 2 and multiply everything by it, the result is this [assuming I take it out from the list afterwards] 4 6 6 10 10 14 14 Now it starts to get tricky. 4 can not be multiplied by 2 again since it will yield 8, which is not one of the factors. However, everything else can be multiplied by 2 to get more factors Basically, in a nutshell, there are certain parts of each list that can not be re-mulitplied. This would require each number to be an object and to store everything that was multiplied to get that number. Not sure if it's the best solution. On August 31 2012 05:24 waxypants wrote:On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Yes it is a recursion. Here is a python solution. I didn't completely test but the results look about right at a glance).
def factors_from_prime_factors(prime_factors):
if not prime_factors:
return []
else:
factors = factors_from_prime_factors(prime_factors[1:]
factors = prime_factors + map(lambda x: x*prime_factors[0], factors)
factors = list(set(factors))
factors.sort()
return factors
The prime factors must be given as a list like [2, 2, 3, 3, 5, 5, 7, 7] in the 44100 case. >>> factors_from_prime_factors([2, 2, 3, 3, 5, 5, 7, 7]) [2, 3, 4, 5, 6, 7, 10, 12, 14, 20, 28, 36, 60, 84, 180, 252, 900, 1260, 6300, 44100] edit: sorting can be taken out or done outside the function, same with the conversion to a set (it just removes duplicates), but I just put them in one function for simplicity and to look nice Hmmm... Looks like you might be missing a few there. http://www.wolframalpha.com/input/?i=factors of 44100This tells me that there are 81 divisors for it, including 22050 [exactly half of it] which I don't see on your list I have an idea for what I need to do. I just gotta code it. On August 31 2012 05:34 zzdd wrote:On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Google Miller Rabin. It will take you maybe an hour to do and is way simpler. Well, looking at Miller Rabin, it seems to be a test to figure out whether a number is prime or not. My assignment is to find all the factors of a large number and list the ones that are prime. I'm not sure how Miller Rabin would help me there, since I already have all the prime factors. You're right, oops. Guess checking for 22050 should have been obvious before I posted it Hmm now I'm going to have to go back and figure out where I went wrong. Ahh was missing one little part. Seems ok now. I know you probably don't need this, but just posting for my own satisfaction
def factors_from_prime_factors(prime_factors):
if not prime_factors:
return []
else:
factors = factors_from_prime_factors(prime_factors[1:])
factors = prime_factors + factors + map(lambda x: x*prime_factors[0], factors)
factors = list(set(factors))
factors.sort()
return factors
>>> factors = factors_from_prime_factors([2, 2, 3, 3, 5, 5, 7, 7]) >>> print factors [2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 25, 28, 30, 35, 36, 42, 45, 49, 50, 60, 63, 70, 75 , 84, 90, 98, 100, 105, 126, 140, 147, 150, 175, 180, 196, 210, 225, 245, 252, 294, 300, 315, 350, 4 20, 441, 450, 490, 525, 588, 630, 700, 735, 882, 900, 980, 1050, 1225, 1260, 1470, 1575, 1764, 2100, 2205, 2450, 2940, 3150, 3675, 4410, 4900, 6300, 7350, 8820, 11025, 14700, 22050, 44100] >>> len(factors) 80 Big thank you to you as well. I will rewrite both methods and compare runtimes to see which one is better.
If you are worried about runtimes for my code it would be best to keep the list L sorted and use binary search to find the correct place for the new result in L (and also at the same time test whether the same number is already in the list due to an earlier product). Otherwise it only calculates the result of each product once which any code pretty much has to do so you can't get it much faster in that regard.
edit:
Sorry, my thinking was a bit incorrect and you do actually certain multiplications many times with this method.
Below is a correction I made and with this I believe you do each necessary multiplication only once.
Now you have the prime factorization where distinct primes are in list P and their respective exponents in list E.
This way you can totally avoid the checking for duplicates, but now keeping the list sorted (which I presume you'd want for printing it out) needs a bit more work.
P <- c(2,3,5,7)
E <- c(2,2,2,2)
L <- c(1)
for(i in 1:length(P))
{
tmp <- c()
for(j in 1:E[i])
{
tmp <- c(tmp,L*(P[i]^j))
}
L <- c(L,tmp)
}
L <- sort(L)
|
Hi everybody. So I'm interested in learning about programming. To be more specific about video game programming. I don't know anything about programming or anything related to it. I was wondering if anyone could help me and show me how to get started. The best way to start learning. Any books you could recommend or websites.
|
On September 02 2012 06:57 ZerO_0 wrote:
Hi everybody. So I'm interested in learning about programming. To be more specific about video game programming. I don't know anything about programming or anything related to it. I was wondering if anyone could help me and show me how to get started. The best way to start learning. Any books you could recommend or websites.
I'd suggest you check out USC's ( University of Southern California ) CS degree requirements. We have one of the best CS GAMES programming degrees.
http://www.cs.usc.edu/brochures/ugcsgm.pdf
Find the courses you're interested in and get the books and read them. Games programming is not SIMPLY about programming. You need to learn data structures, algorithms, linear algebra... etc etc.
|
On September 02 2012 06:57 ZerO_0 wrote:
Hi everybody. So I'm interested in learning about programming. To be more specific about video game programming. I don't know anything about programming or anything related to it. I was wondering if anyone could help me and show me how to get started. The best way to start learning. Any books you could recommend or websites.
First learn the basics:
http://learnpythonthehardway.org/
Then consider looking at some CS courses from universities online (they're free). Good examples would be MIT, Stanford, UW, Berkeley, etc. Hit up some courses in algorithms & data structures, object oriented programming, maybe databases if you feel like it. For example: http://webcast.berkeley.edu/playlist#c,s,All,4BBB74C7D2A1049C and https://www.coursera.org/course/cs101
Then, while you're doing all that, keep yourself entertained with some kind of game programming on the side. Depends on what you want to do. If you have some iOS device and a macbook, you could try doing that. Same with android. Otherwise, there's a couple free java dealies out there aimed at game programming. Lots of choices. You could even do XNA if you dig windows/xbox/whatever.
|
I seem to discuss code things with other people on TL a lot more lately, so rather than infest other channels with that discussion, I went ahead and made an IRC channel on Quakenet (same server as the regular TL channel): #tl.code
Feel free to join if you're interesting in discussing anything related to programming, or if you have quick questions you need answered
|
Does anyone here code in IDL?
|
On September 04 2012 06:20 tec27 wrote:I seem to discuss code things with other people on TL a lot more lately, so rather than infest other channels with that discussion, I went ahead and made an IRC channel on Quakenet (same server as the regular TL channel): #tl.codeFeel free to join if you're interesting in discussing anything related to programming, or if you have quick questions you need answered
should ask tofucake to put it in op
|
On September 04 2012 06:27 Sacred Reich wrote:
Does anyone here code in IDL?
better ask an actual question, i don't know if you'll find anyone actually using this but other people can have ideas too
|
First learn the basics: http://learnpythonthehardway.org/Then consider looking at some CS courses from universities online (they're free). Good examples would be MIT, Stanford, UW, Berkeley, etc. Hit up some courses in algorithms & data structures, object oriented programming, maybe databases if you feel like it. For example: http://webcast.berkeley.edu/playlist#c,s,All,4BBB74C7D2A1049C and https://www.coursera.org/course/cs101Then, while you're doing all that, keep yourself entertained with some kind of game programming on the side. Depends on what you want to do. If you have some iOS device and a macbook, you could try doing that. Same with android. Otherwise, there's a couple free java dealies out there aimed at game programming. Lots of choices. You could even do XNA if you dig windows/xbox/whatever.
Thanks for the help. But I also looked on other websites to see what is a good way to get started. Many people say C is a good way to start other say python. Those are two answers I keep getting. What are the big differences between the two?
|
On September 04 2012 08:15 ZerO_0 wrote:Show nested quote +First learn the basics: http://learnpythonthehardway.org/Then consider looking at some CS courses from universities online (they're free). Good examples would be MIT, Stanford, UW, Berkeley, etc. Hit up some courses in algorithms & data structures, object oriented programming, maybe databases if you feel like it. For example: http://webcast.berkeley.edu/playlist#c,s,All,4BBB74C7D2A1049C and https://www.coursera.org/course/cs101Then, while you're doing all that, keep yourself entertained with some kind of game programming on the side. Depends on what you want to do. If you have some iOS device and a macbook, you could try doing that. Same with android. Otherwise, there's a couple free java dealies out there aimed at game programming. Lots of choices. You could even do XNA if you dig windows/xbox/whatever. Thanks for the help. But I also looked on other websites to see what is a good way to get started. Many people say C is a good way to start other say python. Those are two answers I keep getting. What are the big differences between the two?
python is written much more like normal human language, C has all kinds of weird ; and - - and less intuitive stuff inside the actual language. People probably say learn C because (a) its a hell of a lot harder and (b) more 'hard core' applications are run on C than on python, for now.
Honestly I do python because the first thing you really need to learn is how to think in terms of building a computer program, and being distracted by the clunky syntax is distracting. On the other hand if you master C then python will probably seem like a breeze.
Others pointed out courseara but you should also check out udacity.
|
^ I think the above is basically correct. Python is a good starting point because things don't get in your way as much. Lisp purists will of course argue that Python still gets in your way and you should start out with Lisp or Scheme or something.
+1 to udacity. You also may want to check out khanacademy and see if they have any decent comp sci stuff
coursera.org
udacity.com
khanacademy.org
On September 04 2012 08:15 ZerO_0 wrote:Thanks for the help. But I also looked on other websites to see what is a good way to get started. Many people say C is a good way to start other say python. Those are two answers I keep getting. What are the big differences between the two?
The language does not matter a whole lot. In the end, once you know what you're doing, you should be able to pick up a new language with decent proficiency in a week or two.
|
The reason people recommend C is not simply because it is a harder, but because it requires you to actually to learn and understand what you are doing before you can really do anything substantial. I advocate this approach of starting with C if you really want to understand the whole picture very well. Python is very high-level and while I love it, I question whether it is a good starting point. I understand that it is a lot simpler for a nooby and you can program at a very high level and accomplish a lot of things easily with very little code and very little understanding of what the entire system is built on. That's why I love it when I just want to bang out some quick tool or proof of concept. It boils down to a top-down (Python as first language) vs. a bottom-up approach (C as first language). I think in the long run it's easier to start at essentially the bottom (C) and build upon that, than it is to start at the top (Python) and work your way down when you inevitably need to. I find that people have a hard time coming down when they've started at the top, and they often take a lot longer to get a good understanding of the whole picture.
|
|
|
|
|
|
EPT
