Factoring

TeleMad · April 21, 2005

I'll time test this function tonight using 10,000 pseudo-randomly generated numbers between 1 and a quadrillion, posting the MIN, MAX, and AVG time intervals when it completes.

And here are the times.

Min = 0.146 seconds

Max = 5.709 seconds

Avg = 0.245 seconds

Based on those numbers, my algorithm can determine whether a number up to 1 quadrillion is prime in a maximum of about 6 seconds.

PS: I'll post the individual results as I did before ... if asked, but I don't think posting 10,000 rows of data is the thing to just up and do.

Qfwfq · April 21, 2005

No, I won't ask you to post it because I know enough about factoring to understand in terms of your max and average.

At least you are improving now, trial dividing by primes only, not by every bloody odd number. My C++ class Looong does this for huge numbers providing the prime factors are no larger than 4G, which is impossible for a non-prime not exceeding 18,446,744,073,709,551,616. What would you call that, 18 pentillion? Thus if I give it a number less than that and it throws a 'factor too big' exception, I have a positive primality test for that number. Of course, if that had been my purpose I would have made it return a boolean value.

Now I see that yesterday I was still misled by things you said, you do have a one-time setup, after all:

FUNCTION CreateSieve(lnMaxNumber)
* One-time setup
CLOSE ALL
SET SAFETY OFF
CREATE TABLE sieve (prime L(1))
FOR lnLcv = 1 TO lnMaxNumber
   	 INSERT INTO sieve (prime) VALUES (.T.)
ENDFOR
UPDATE sieve WHERE RECNO() = 1 SET prime = .F.
UPDATE sieve WHERE RECNO() % 2 = 0 AND RECNO() > 2 SET prime = .F.
lnHighestFactor = CEILING(SQRT(lnMaxNumber))
FOR lnLcv = 3 TO lnHighestFactor STEP 2
	GO (lnLcv)
	IF (prime)
		UPDATE sieve WHERE RECNO() % lnLcv = 0 AND RECNO() > lnLcv SET prime = .F.
	ENDIF
ENDFOR
INDEX ON prime TAG prime
CLOSE ALL
ENDFUNC

You simply haven't stated how long it takes to execute. It's what my algorithm can do in a couple of seconds, for Max = 50 million. So the 100+ ms times in that table you posted are a lookup, after all.

BTW, now that I notice, you call your functions CreateSieve, TimeSieve, NextPrime and IsPrime.

Not up with today's naming conventions! :)

TeleMad · April 21, 2005

Now I see that yesterday I was still misled by things you said,

I didn't mislead you, you just didn't understand. That's your fault, not mine.

Qfwfq: ... you do have a one-time setup, after all:

And that it took you this long to figure something that obvous out loses you 1,000 points!

Qfwfq: You simply haven't stated how long it takes to execute.

Yes I have, multiple times, and I'll state it again. The one-time setup took 0 milliseconds of user-needed CPU time: it didn't consume even 1 CPU cycle to perform during program execution.

Qfwfq: It's what my algorithm can do in a couple of seconds, for Max = 50 million.

Yeah, during program execution!

So for this runtime setup yours takes more than a trillion times longer than mine :-)

Qfwfq: So the 100+ ms times in that table you posted are a lookup...

There goes another 1,000 points for you! I can't believe you didn't realize something that blatantly obvious before now.

Qfwfq: ... after all.

After all what? It's not my fault YOU can't follow EXTREMELY simple and straightforward code.

PS: I've got one exame and two finals coming up next week so I'll be too busy from now until then to point out more of your failings. Don't worry, I should have plenty of time to do so in a little over a week.

TeleMad · April 21, 2005

Qfwfq: Now I see that yesterday I was still [being a dunce], you do have a one-time setup, after all:

Gee, I had been trying so hard to hide that ... NOT!!!!!

Even a half-wit would have immediately realized that mine did have a one-time setup, considering all the times I said so.

TeleMad: It's divided into two parts. First, there's a one-time setup that populates a table with a boolean value for Prime for all natural numbers between 1 and 500,000. Again, that's done only once and then forgotten about: it's a one-time time penalty. …

1) ONE-TIME SETUP

TeleMad: PPS: Okay, so I actually set this up and ran it: couldn't resist. It took only a minute or so for the one-time setup.

TeleMad: After making a couple optimizations to the one-time setup algorithm …
FUNCTION CreateSieve(lnMaxNumber)
* One-time setup

TeleMad: My one-time setup was performed (1) only once, and (2) at night, when the computer would have otherwise been completely idle.

My one-time investment reaped huge dividends and it didn't cost me even 1 millisecond of needed CPU time to accomplish.

I prepared, just once, ahead of time DURING OTHERWISE UNPRODUCTIVE TIME so that I could be MORE PRODUCTIVE during runtime. Bosses love that kind of thing: you should give it try!

TeleMad: 2) I said it took my one-time 'setup' algorithm 0 milliseconds of needed CPU time to complete (setup here as in how I've been using it most frequently).

TeleMad: Initial setup time was 0 milliseconds of needed CPU time.

Not the sharpest tool in the shed, are you Qfwfq! ROTFLMAO!!!

Qfwfq · April 22, 2005

Even a half-wit would have immediately realized that mine did have a one-time setup, considering all the times I said so.

You said many contradictory things, interpreted my mention of setup as meaning writing and debugging, and I'm not a half-wit, por favor.

If you got so upset at being unable to understand my algorithm that you blame it on my code and accuse it of being cryptic as hell, I'm sorry. It isn't an excuse for you to be insolent.

Don't think I have been less busy than you are going to be on this exam, before today and yesterday I really couldn't take much time to read your code and even remember with certainty next day or, instead, go back and read it again.

Even if your claim about CreateSieve running in less than 1 ms were plausible, you might wish to study arithmetic after you've done with your exams. Good luck on them, I suspect you'll be needing some. A couple of seconds isn't more than a trillion times a millisecond and, if you haven't measured how much less than 1 ms, you've no grounds for saying more than a trillion. Are you sure that you are the best tool in the shed?

If it really was less than a millisecond, why gloat so much about the never before heard of idea of exploiting idle time at night? Especially if it was about a picosecond. That ain't the typical thing that is left to night batches!

TeleMad · April 23, 2005

Qfwfq: You said many contradictory things…

No, my statements were all consistent with one another. The problem lies with your inability to understand what was said, not with what I said.

It's so sad. You made a fool out of yourself and now you follow that up by trying to blame me for your shortcomings.

Qfwfq: … [you] interpreted my mention of setup as meaning writing and debugging..

Grow up.

1) YOUR statement was ambiguous. YOU are the source of any problems on this particular issue.

2) I did not interpret your mention of setup as meaning writing and debugging, but rather as POSSIBLY meaning writing and debugging.

Please stop trying to blame others for your failures and shortcomings.

TeleMad · April 23, 2005

Qfwfq: If you got so upset at being unable to understand my algorithm…

Uhm, where did I say I tried but was unable to understand your algorithm? Can you point it out to us? Nope. You’re just being childish, and once again trying to shift attention away from your shortcomings.

Qfwfq: … you blame it on my code and accuse it of being cryptic as hell, I'm sorry.

Your code IS cryptic as hell and it does NOT follow several coding standards/conventions.

Qfwfq: Even if you claim about CreateSieve running in less than 1 ms were plausible…

Can’t you understand English? Go back and read what I actually said.

Qfwfq: … you might wish to study arithmetic after you've done with your exams.

Why? Because YOU are still unable to follow what I’ve been saying all along? Grow up.

No my friend, the problem is not my math, but rather your inability to understand simple concepts.

If anyone needs to brush up on math, it’s you. Don’t worry, I’ll explain below.

Qfwfq: A couple of seconds isn't more than a trillion times a millisecond …

And I didn’t state or imply it was.

Why do you insist on misinterpreting my perfectly clear statements? You obviously still don’t understand what I have been saying, consistently, for the post ‘umpteen’ posts. You shouldn’t even be commenting: you haven’t a clue what it is you are responding to.

Now concerning math.

Even a mere child knows the following:

1) 0 x 1,000,000,000,000 = 0

2) 0 < any positive number

That’s all the math one needs to know to see that I am right and you are wrong.

Since I said that my one-time setup algorithm takes 0 milliseconds during runtime (since it is a one-time setup that is performed before users use the program itself), then your couple-of-seconds for setup during program execution IS more than a trillion times what my setup algorithm takes during program execution.

Qfwfq: Are you sure that you are the best tool in the shed?

Much sharper than you, as anyone who is following these exchanges can clearly see.

Qfwfq: If it really was less than a millisecond, why gloat so much about the never before heard of idea of exploiting idle time at night?

Good lord dude, get a clue. You should try to understand what you are replying to; you are only embarrassing yourself more and more.

TeleMad · April 23, 2005

Qfwfq: Good luck on [your exams], I suspect you'll be needing some.

Now you’re just being childish.

When I’ve said something negative about you in this thread it’s because YOU have earned it: that is, YOU have posted something that DESERVES to be called foolish.

On the other hand, you have absolutely no basis for your negative comment: what chemistry and/or biology blunders have I made in this thread? None.

And for your information, I don’t need luck – I’ve got an excellent handle on my classes. The tests for which I have received graded results so far this semester are as follows:

1) Human anatomy & physiology: 93, 92, 93, and an 89 = 91.75 average

With only two exams remaining I need to average just 86.5 on them to come out with yet another 4.0. Relative to my existing grades, I’d have to badly flub up the last two to get even a ‘B’.

2) General chemistry II: 97 and 100 = 98.5 average.

The last test I took, on this past Wednesday, hasn’t been returned yet but I know I aced it as well. Just for the sake of argument, suppose I made only a 90 on that third exam. To end up with an ‘A’ in this class I need to get only a 73 on the final to come out with yet another 4.0.

And in case you missed it, I already stated here at these forums that I graduated with a perfect 4.0 cumulative GPA for my first BS. And so far, looks like I will maintain that perfect 4.0 cumulative GPA for my second BS too.

And, I scored in the 99th percentile in the standardized BASE exams for college juniors.

Oh, and I am a candidate master at correspondence chess.

So your comment is not only childish and unfounded, but very misplaced.

TeleMad · April 23, 2005

Good example of apples and oranges! You say:

"Uhm, because maintainability should always be taken into consideration"

"but your hardware-specific issues - cache misses and page faults - are hardly ever taken into consideration"

The difference boils down to that at the most: 'should' vs. 'hardly ever'.

Maintainability should always be taken into consideration when writing code, but your hardware-specific issues - cache misses and page faults - are not taken into consideration when comparing algorithmic efficience.

TeleMad · April 23, 2005

I don't want to say your algorithm is less efficient than the simpler one but ...

Well what DO you want to say about their relative efficiencies? Here are your choices concerning alexander's and my C++ algorithms that perform the same function. Which one do you claim is correct ... and you should be prepared to support your choice.

1) TeleMad's is more efficient than alexander's

2) alexander's is more efficient than TeleMad's

3) TeleMad's and alexander's are equally efficient

I've supported (1) in more than one way. If you choose either of the other ones the burden of proof lies on your shoulders.

Qfwfq · April 26, 2005

Good example of apples and oranges! You say:

"Uhm, because maintainability should always be taken into consideration"

"but your hardware-specific issues - cache misses and page faults - are hardly ever taken into consideration"

The difference boils down to that at the most: 'should' vs. 'hardly ever'.
Maintainability should always be taken into consideration when writing code, but your hardware-specific issues - cache misses and page faults - are not taken into consideration when comparing algorithmic efficience.

Here we are again, apples and oranges, when writing code vs. when comparing algorithmic efficience.

How about performance tuning? Certainly not less relevant to Alexander's purpose than customer issues were.

Qfwfq · April 26, 2005

I shall bother no further with your pure insolence.

Now concerning math.

Even a mere child knows the following:

1) 0 x 1,000,000,000,000 = 0

2) 0 < any positive number

That’s all the math one needs to know to see that I am right and you are wrong.

Since I said that my one-time setup algorithm takes 0 milliseconds during runtime (since it is a one-time setup that is performed before users use the program itself), then your couple-of-seconds for setup during program execution IS more than a trillion times what my setup algorithm takes during program execution.

Oh, so that's what you meant!!! Do you call that a mathematical argument for saying that your setup time is a trillinonth of mine? Learn to communicate effectively and quit accusing me of being childish and telling me to grow up.

It's easy to save my sieve to a file and read it in further processes but it's hardly worth bothering in some cases, especially for the sieve up to only 50 million. I had devised that function to make it a bit less necessary, for the purposes I had then intended.

Once the sieve is set up, my lookup times are so tiny that it doesn't make sense to measure them in milliseconds, even on my old crate at home the average was around 800 in a millisecond. On the faster machine I'm on now it does well over 6000 each millisecond, on runs of millions of lookups. That's the advantage of having an array of flags in virtual memory, if one wants to do some heavy factoring.

I tried a test similar to the one you ran, for numbers less than the square of 50 million. It outruns yours, once the sieve is executed the max time is hardly a second on this machine I'm using. Even adding the two or three seconds for the sieve, that totals less than the max that you posted, after that it is decidedly less. In this range, then, it's hardly worth saving the file. On a run of the 1000 numbers up to the square of 49999991 the average time is hardly 40 milliseconds. Right now I'm running it on a million such numbers.

I meant to post the .exe so you can try running it but I had to zip it, there's the code too, as some choices in

main() might be changed as you please.

Your code IS cryptic as hell and it does NOT follow several coding standards/conventions.

You got upset because you were unable to understand my algorithm and you blamed it on naming conventions. Don't accuse me of blaming any shortcomings of mine on you.

I'm not interested in your accademic scores either and I'm sure you're not interested in mine, I'm not childish enough for that type of gloating. Neither am I a dude, s'il vous plait.

Qfwfq · April 27, 2005

I had to re-start the run of a million before leaving here, as I couldn't use enterprise IDEs and so on while it was running. The statistics are:

max time < 2.525 seconds; count = 1000000; 0.031 < ave < 0.032 seconds

time is around a second for almost all primes, suggesting the max time is due to other activity on the machine. Of course, one could put the output calls in the while block in a condition on t, the output file is a 45 megabyte whopper, I hadn't predicted doing the million long run when I compiled it, I only thought of separating output for redirection.

TeleMad · April 30, 2005

Gee Qfwfq, you seemed to have "overlooked" this post. Here, let me ask you again.

Qfwfq: I don't want to say your algorithm is less efficient than the simpler one but ...

Well what DO you want to say about their relative efficiencies? Here are your choices concerning alexander's and my C++ algorithms that perform the same function. Which one do you claim is correct ... and you should be prepared to support your choice.

1) TeleMad's is more efficient than alexander's

2) alexander's is more efficient than TeleMad's

3) TeleMad's and alexander's are equally efficient

I've supported (1) in more than one way. If you choose either of the other ones the burden of proof lies on your shoulders.

TeleMad · April 30, 2005

Oh, so that's what you meant!!!

As any halfwit would have known all along. Sorry if your mental capabilities remained below that threshold throughout these exchanges.

Qfwfq: Do you call that a mathematical argument for saying that your setup time is a trillinonth of mine?

Are you REALLY as dumb as your statements in this thread make you appear to be?

Qfwfq: Learn to communicate effectively,,,

I have communicated effectively: you just aren't up to grasping VERY SIMPLE concepts.

My impression of Qfwfq on Jeopardy (as in the Celebrity Jeopardy sketches from SNL).

Alex: Okay Qfwfq, you control the board. Pick your category.

Qfwfq: Alex, I'll take "The number 8" for $100.

Alex: I am the number that sounds like ate.

Qfwfq: <no response>

Alex: Okay, you still control the board. Pick again.

Qfwfq: Alex, I'll take "The number 8" for $200.

Alex: I am how many apples little Timmy would end up with if he started with 4 and Jenny gave him 4 four more.

Qfwfq: <no response>

Alex: <sigh> Okay Qfwfq, you still control the board. Pick again.

Qfwfq: Alex, I'll take "The number 8" for $300.

Alex: 2^3

Qfwfq: <no response>

Alex: <deeper sigh> Okay Qfwfq, you still control the board. Pick again.

Qfwfq: Alex, I'll take "The number 8" for $1,000.

Alex: The squ.... oh never mind. Look Qfwfq, just buzz in and say "What is the number 8?". Do you understand? Just buzz in and say the words, "What is the number 8?"

Qfwfq: <no response>

Alex: <frustrated> Look you @#@^%#&^%$ the answer to all those questions was 8 .. what is the number 8!!! Get it????

Qfwfq: Oh, so it was 8 after all!

TeleMad · April 30, 2005

Qfwfq: [blah blah blah faster blah blah blah]

So you FINALLY ‘figured out’ what I already told you a week ago?

TeleMad (04/18/2005): General C++ code is considered to execute much faster than VFP code.

Congratulations! You’re starting to grasp things only 7 days after the fact!

Qfwfq · May 2, 2005

Well what DO you want to say about their relative efficiencies?

What I meant to say, way back then, was that I had no intention of discussing the comparison between your & Alexander's code. I guess you hadn't gathered that.

General C++ code is considered to execute much faster than VFP code.

A well known fact.

You did post your times, as if you wanted to compare them, and I offered the possibility. The difference isn't only due to the choice of language but also to the different type of lookup.

As any halfwit would have known all along. Sorry if your mental capabilities remained below that threshold throughout these exchanges.

Ignored, along with the rest.

Sign In

Factoring

Recommended Posts

TeleMad

Top Posters In This Topic

Popular Days

Top Posters In This Topic

Popular Days

Qfwfq

TeleMad

TeleMad

Qfwfq

TeleMad

TeleMad

TeleMad

TeleMad

TeleMad

Qfwfq

Qfwfq

Qfwfq

TeleMad

TeleMad

TeleMad

Qfwfq

Join the conversation

Browse

Activity