mersenneforum.org Help with series convergence in Fermat method of factoring
 Register FAQ Search Today's Posts Mark Forums Read

2017-03-27, 04:26   #34
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

89D16 Posts

Quote:
 Originally Posted by CRGreathouse I just typed it up, I've never had need of a function like that so far.
Then, you are a much better programmer than I am.

2017-03-27, 04:30   #35
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

220510 Posts

Quote:
 Originally Posted by CRGreathouse NO! The reason you want those functions is that when you compute sqrt() or log() you move the calculation from the integers (t_INT) to the reals (t_REAL), and the conversion back to the integers is imperfect. PARI tries to detect situations where there is insufficient precision to correctly determine a floor or ceiling but it's not guaranteed to do so correctly, and you can pretty easily find exceptions (it's a fact of life when dealing with floating-point numbers). But when you have sqrtint and logint, you remain in the integers the whole time, and you're guaranteed to get the correct answer. So just because mathematically the two would be equal when computed with infinite precision does not mean that the two are equal when computed with finite precision, and so the functions are most certainly not redundant. I was being careful when I wrote logint(x\=1,2) rather than log(x)\log(2). Before logint I would typically write more complex expressions like log(x\1 + 0.5)\log(2) which, while still subject to rounding, were less likely to round the wrong way. Doing it truly correctly and quickly requires actual numerical analysis... or just using the function designed specifically for that purpose.
Thank you for the insight. Given that, then, are there more proper codes for:

upperPower =ceil(log(n)\log(2))
and
runningBase=ceil(sqrtn(n ,i))

 2017-03-27, 04:31 #36 CRGreathouse     Aug 2006 3×1,993 Posts Also, FWIW, my version of your above program Code: np(x)=->if(x<=1,return(1));my(best=(sqrtnint(x-1,3)+1)^3,t);x=ceil(x);for(e=4,logint(x,2),t=(sqrtnint(x-1,e)+1)^e;if(t
 2017-03-27, 04:35 #37 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 32×5×72 Posts Can you be more specific on the bug? What value of n gives the wrong result?
2017-03-27, 04:35   #38
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by a1call Thank you for the insight. Given that, then, are there more proper codes for: upperPower =ceil(log(n)\log(2)) and runningBase=ceil(sqrtn(n ,i)) Thanks in advance.
Good question! I've always found this annoying.

If n is an integer which is at least 2, then you can use
and if n and i are integers which are at least 1, you can use
runningBase = sqrtnint(n-1,i)+1

2017-03-27, 04:37   #39
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by a1call Can you be more specific on the bug? What value of n gives the wrong result?
2, 3, 4, 5, 6, and 7.

Code:
apply(nextPower3RN, [2..7])
%1 = [4, 9, 16, 25, 36, 49]
4, 9, 25, 36, and 49 aren't even 3rd or higher powers. 16 is a fourth powers but the third power 8 is smaller.

2017-03-27, 04:39   #40
CRGreathouse

Aug 2006

597910 Posts

Quote:
 Originally Posted by a1call Then, you are a much better programmer than I am.
Heh.

More experienced in this aspect of programming, more likely. But we all have our strengths. I've been learning a new language lately and I'm fumbling about like anyone else would be.

 2017-03-27, 05:34 #41 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 32×5×72 Posts Thank you for the bug catch. Here is the corrected code: Code: \\"Efficient" nextPower3RN(n)={ my(upperPower ,i,smallestPower=n^2,theBase,theExp,runningBase,theCandidate); if(n<5,print("\n",8," = ",2,"^",3);return(8);); if(ispower(n)>2,n=n+1); upperPower =ceil(log(n)/log(2)); for(i=3,upperPower, runningBase=ceil(sqrtn(n ,i)); theCandidate=runningBase^i; if(theCandidate2,m=n+1); while(ispower(m)<3, m=m+1; ); print(m); return(m); } I had a \ instead of a / and did not treat n differently when it was already a power of 3 or more and did not treat n< 5 differently. Last fiddled with by a1call on 2017-03-27 at 05:35
2017-03-27, 14:47   #42
Dr Sardonicus

Feb 2017
Nowhere

7×13×59 Posts

Quote:
 Originally Posted by CRGreathouse NO! The reason you want those functions is that when you compute sqrt() or log() you move the calculation from the integers (t_INT) to the reals (t_REAL), and the conversion back to the integers is imperfect. PARI tries to detect situations where there is insufficient precision to correctly determine a floor or ceiling but it's not guaranteed to do so correctly, and you can pretty easily find exceptions (it's a fact of life when dealing with floating-point numbers). But when you have sqrtint and logint, you remain in the integers the whole time, and you're guaranteed to get the correct answer.
It would be difficult to overstate the importance of distinguishing between approximate and exact variable types. An example arose here, in a thread devoted to the topic of Fermat's factorization method. A Pari script I copy-pasted from a paper and ran (after replacing the stylized ^ symbols with plain-text), produced an error message when it successfully detected insufficient precision. (I bumped up the precision and ran it again, and got the expected results).

Computing Galois groups can also come to grief if approximate numerical roots have insufficient precision.

Number field calculations largely rely on exact polynomial arithmetic. For example, Mod(x, x^2 - 2) is an exact square root of 2...

 2017-10-03, 02:40 #43 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 2·32·233 Posts I'd like to renew this thread just long enough to revisit the following. I've probably missed something in my studies, or maybe this just isn't doable. Anyway: I'm trying to figure out how to calculate where the coincidence of two series will happen. The series grow by a known progression. I know the starting integer and the progression for each series, but I can't figure out a way to calculate coincidence. Is that because it can't be done, or because I don't know enough? series1 is 2704+105+107+109+111... series2 is 2691+17+19+21+23+25... series1 will equal 2916 at 2705+105+107 series2 will equal 2916 at 2691+17+19+21+23+25+27+29+31+33 Is there a way to calculate the value 2916 directly, if it is unknown? IOW, can 2705+105+107... = 2691+17+19... be calculated instead of stepping through each to coincidence? Obviously, I'll want to be able to do this with much larger integers, but these small ones illustrate my query. Thanks for any replies...
 2017-10-03, 05:52 #44 CRGreathouse     Aug 2006 3×1,993 Posts If you can compute them term-by-term, and if each summand is a positive integer, it's not hard. Code: coincidence(f, g, terms)= { my(n1, n2, s1, s2); while(max(n1,n2) < terms, if(s1==s2, print("Sum of the first "n1" terms equals sum of the first "n2" terms"); s1 += f(n1++); s2 += g(n2++) , if(s1if(n>1, 2*n+101, 2704), n->if(n>1, 2*n+13, 2691), 1e6);`

 Similar Threads Thread Thread Starter Forum Replies Last Post wildrabbitt Math 3 2016-08-16 08:38 rdotson Miscellaneous Math 0 2007-07-27 10:32 philmoore Math 131 2006-12-18 06:27 Carlos Programming 0 2005-09-11 12:50 LoKI.GuZ Math 10 2004-11-28 03:07

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

Tue Jan 25 05:08:48 UTC 2022 up 185 days, 23:37, 0 users, load averages: 2.15, 1.85, 1.52