mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operation Billion Digits

Reply
 
Thread Tools
Old 2015-09-27, 16:01   #12
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

32·1,093 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I am curious. Why do you think that not having taken calculus is relevant?
The question you ask has nothing to do with calculus.
I agree with your post in general but...

"Not haven taken calculus" might be interpreted as a statement which suggests the general level of mathematical education which may be assumed for further discussion.
xilman is offline   Reply With Quote
Old 2015-09-27, 20:47   #13
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

163158 Posts
Default

Quote:
Originally Posted by xilman View Post
I agree with your post in general but...

"Not haven taken calculus" might be interpreted as a statement which suggests the general level of mathematical education which may be assumed for further discussion.
Perhaps. But the second half of that sentence "so I hope it's not too complex"
tends to indicate something else.
R.D. Silverman is offline   Reply With Quote
Old 2015-10-03, 05:41   #14
FloatingPoint
 
Sep 2015

3 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I am curious. Why do you think that not having taken calculus is relevant?
The question you ask has nothing to do with calculus.
Well, I guess the easiest way to put it is that I have not one single clue what the answer to my question involves, and in the two colleges I've been to, the classes below calculus are not really advanced and I assumed the answer would be somewhat advanced, and hence I asked for it to be put in layman terms if possible. Does this answer satisfy?

Now I'm curious if you're one of those people who have a hard time putting yourself in another persons shoes.

Quote:
Originally Posted by R.D. Silverman View Post
(1) A complex subject It can be, but it isn't always. Any area of math can be simple
or it can be complex. You are confusing "elementary" with "complex". Elementary problems
in math can be very complicated. Very advanced mathematics can be quite simple.
I don't think I'm confusing "elementary" with "complex". I'm pretty sure you're confusing "subjective" with "objective". I don't know a thing about it, therefore if you talk to me about it, there's a good chance I couldn't follow. Of course I can learn about it and it will no longer be complex to me, but until then, it remains complex.

By the way, you are telling me calculus can be complex, and then also telling me elementary problems in math can be complex. See the issue there?

Quote:
Originally Posted by R.D. Silverman View Post
(2) It also implies that you think you will better understand "complicated" mathematics after
you take calculus. I can assure you that this is not true.
You seem to have this recurrence of lacking empathy in your statements. Calculus is complicated mathematics to me, therefore if I learn calculus, I will better understand complicated mathematics. Practice empathy, it'll help you in life, I can assure you this.

Quote:
Originally Posted by R.D. Silverman View Post
BTW. Testing billion digit arbitrary numbers for primality is beyond the range of current
algorithms and computers. It is possible that with moderate effort one can show that a
billion digit number isn't prime, but such a demonstration requires luck.
Cool thanks.
FloatingPoint is offline   Reply With Quote
Old 2015-10-03, 22:02   #15
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1090510 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
A quick and dirty calculation estimates it would take a quad core 4GHz machine working *perfectly* for about 15.5-16 years to run a single test
Could you outline your math here?

Quote:
I don't know if mlucas, glucas, or CUDAlucas are set to handle a number this large. I don't think the current version of Prime95 is. You would want to do ~ 1-2 years of factoring on a GPU first, then about a year's worth of P-1 with a massive amount of memory (128GB ?).
Mlucas can handle numbers that large, but only of Mersenne and Fermat form. I am currently ~80% done running a Pe'pin test on F29 (~160 Mdigit) using all 4 cores of my 3.3GHz Haswell quad; total time will end up ~18 months. That is a first run using FFT length 30M; I still need to do a DC, for which I will use a slightly larger FFT length of 32M, ensuring 'different data' beyond the first handful of iterations.

(F29 has a known small factor; I intend to use the Pe'pin residue for future fast cofactor-PRP tests.)

To the OP: You still haven't commented on whether your number has any kind of special algebraic form. If so, what is it? If not, in what context does the number arise?

Last fiddled with by ewmayer on 2015-10-03 at 22:04
ewmayer is offline   Reply With Quote
Old 2015-10-04, 03:37   #16
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

22·3·647 Posts
Default

Quote:
Originally Posted by ewmayer View Post
Could you outline your math here?
I just used James H's tool to get the GHz days for a ~1G digit Mersenne. Then did the math for 4 cores and days to years.
Uncwilly is offline   Reply With Quote
Old 2015-10-04, 08:08   #17
axn
 
axn's Avatar
 
Jun 2003

11B516 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
I just used James H's tool to get the GHz days for a ~1G digit Mersenne. Then did the math for 4 cores and days to years.
It is off. Way off.

For 33,219,000, it gives. 37.7.
For 332,190,000, it gives 4,941. About 131x. Sounds right-ish.
For 3,321,900,000, it gives 91,629. At the very least it should be 100x the previous, so about 500,000. In practice, it might be 150-200x?
axn is offline   Reply With Quote
Old 2015-10-04, 13:06   #18
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

838310 Posts
Default

Indeed it is an order of magnitude off there. It should be ~900k, not ~90k. If you double the exponent, your time more than quadruples, because you will have a (roughly, more than) double time for each iteration and a double number of iterations to do. In practice, it is more that that, and the FFT won't scale linearly for so big range. Tripling the exponent you have about 10-12 times longer the time (and not 9 times, as for squaring) and it sounds reasonable that if the exponent grows 10 times you may have 100x for small expos, but you will have 150x for average expos, and 200x for big expos. I think ~4.5k*~200x is the right number here, giving about 900k. And that assuming we have already the soft and hardware able to do it.
LaurV is online now   Reply With Quote
Old 2015-10-04, 20:37   #19
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3×5×727 Posts
Default

Quote:
Originally Posted by axn View Post
It is off. Way off.
That was the reason for my double-take: While my code is still slower than George's, it's not *that* much slower, and O(n^2 * lg(n) * lg lg(n)) - extrapolating my current F29 timings to Gdigit (I was away from home, thus not able to simply do a timing run at the needed length) gave a runtime estimate much higher than the one Uncwilly posted.
ewmayer is offline   Reply With Quote
Old 2015-10-05, 00:07   #20
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

737310 Posts
Default

Quote:
Originally Posted by FloatingPoint View Post
Well, I guess the easiest way to put it is that I have not one single clue what the answer to my question involves,
Number theory, group theory as a sub-topic of modern algebra, and the theory of computation/computer algorithms.

Quote:
and in the two colleges I've been to, the classes below calculus are not really advanced
So I presume that you have not really been exposed to any math at all beyond basic high school algebra?

BTW, in my experience classes "below" calculus are NOT properly college level subjects, except perhaps
at local community colleges (which are usually just over-blown high schools for people who struggled in
high school]

Most colleges start with calculus, and pre-calculus level math is assumed as an admisison criteria. It is true that
remedial classes can be and are offered, but they are not usually taken for credit.

Quote:
and I assumed the answer would be somewhat advanced, and hence I asked for it to be put in layman terms if possible. Does this answer satisfy?
On what basis did you make the assumption that the answer would be advanced??? You don't
know enough to whether it will or won't be advanced. It is merely something that YOU HAVE NOT STUDIED.

We are discussing the philosophy of mathematical study here. 'Advanced' is not well defined.
Single-variable calculus is not generally considered an advanced subject. You personally may
consider it advanced, but it really isn't. One does need to approach its study with a POSITIVE
ATTITUDE rather than "it's going to be too complicated for me". I have seen too many people
fail at mathematical study because they view it with fear and apprehension. Math is not unique
in this regard; the same is true in any technical subject.

Basic Number theory, as a subject certainly can be studied before taking calculus. It can even be taken
prior to studying modern algebra, although number theory and algebra are very much inter-twined.

Quote:
Now I'm curious if you're one of those people who have a hard time putting yourself in another persons shoes.
Why are you making this personal? It isn't.


Quote:
I don't think I'm confusing "elementary" with "complex".
Yes, you are.

Quote:

I'm pretty sure you're confusing "subjective" with "objective". I don't know a thing about it, therefore if you talk to me about it, there's a good chance I couldn't follow. Of course I can learn about it and it will no longer be complex to me, but until then, it remains complex.
This is abad attitude. i.e. viewing something as 'complex' before studying it.


Quote:
By the way, you are telling me calculus can be complex, and then also telling me elementary problems in math can be complex. See the issue there?
I see no conflict. Parts of calculus are very simple. Parts of it are very complex. The same is true of pre-calculus
mathematics.


Quote:
You seem to have this recurrence of lacking empathy in your statements.
This NOT an emotional discussion. I am discussing complexity in the study of mathematics.

Quote:
Calculus is complicated mathematics to me,
This is not the viewpoint most technical people will have. First year calculus is rather cookbook.


Quote:
therefore if I learn calculus, I will better understand complicated mathematics. Practice empathy, it'll help you in life, I can assure you this.
Learn to accept what others teach you. It will help you in life, I assure you. Basic calculus is not considered
'complicated' by the general technical community.
R.D. Silverman is offline   Reply With Quote
Old 2015-10-05, 02:36   #21
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

399410 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Most colleges start with calculus, and pre-calculus level math is assumed as an admisison criteria. It is true that
remedial classes can be and are offered, but they are not usually taken for credit.
This is not true, at least in the USA. College algebra is a standard general-education course for graduation/college-credit, and precalculus (college alg plus trig, roughly) is a standard course for entering freshmen. I teach at a research university (University of California), and fewer than half our entering freshmen are ready for calculus upon entry. Our view is that high schools do such a poor job with precalc and calculus that the majority of students must re-take precalc at the university. My experience at both state-school and private universities is the same, below elite level. The Ivy league and other top-20 universities may do it the way RDS remembers, but the vast majority of US universities offer precalc for college credit, and expect a substantial number of students to need to take it.

At colleges that admit students below the top 15% of their HS graduating class, precalc is not even an admission requirement. It amazes and disappoints me how many high school counselors advise mediocre students to take statistics instead of precalc to "help their GPA". Regional level private colleges and state-schools have little choice but to work around this lack of preparation.
VBCurtis is offline   Reply With Quote
Old 2015-10-05, 03:11   #22
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

83·101 Posts
Default

At my time, we did precalculus (mainly differentials, limits, series) in grade 11, and calculus (Riemann integrals, etc, what is called "ap calc" over the big pond) in grade 12. At the university we repeated that all in the first year, at higher level (included Lebesgue integrals, etc), and moved to partial derivatives and more complicated stuff in the second year (which subject I failed two times, and passed the third time with mark 7 (of 10), haha). We also did elementary probabilities theory in grade 12, and much high level statistics during the 2nd and 3rd (of 5) college years.

Related to your last paragraph, my girl (who goes to an international school here) did precalculus in grade 11, but to a much lower level that I used to, and she didn't like it (in spite of getting the highest mark, for which the reason was mainly endless crying evenings when we did the homework together) so she took statistics this year (grade 12) exactly as you said, to avoid calculus. Up to now, they are doing very elementary stuff, like graphing data and interpreting graphs. I don't think this can "survive" a "test" for a possible admission, at any university. But my wife tells me I am too exaggerate, and I am thinking "well, maybe there are different times now..."

My girl took SAT by the way, the day before yesterday. We are waiting for the results...

Last fiddled with by LaurV on 2015-10-05 at 03:15
LaurV is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fast isPrime() for n < 2^32 SPWorley Computer Science & Computational Number Theory 35 2018-07-28 13:02
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
Number of Factors for a Mersenne Number kurtulmehtap Math 12 2010-05-03 14:02
First check and double check llrnet servers. opyrt Prime Sierpinski Project 3 2009-01-02 01:50
How to check if a number is a Mersenne prime ? Unregistered Software 6 2004-06-19 08:18

All times are UTC. The time now is 05:29.

Wed Apr 1 05:29:53 UTC 2020 up 7 days, 3:02, 0 users, load averages: 1.12, 1.21, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.