mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2017-03-27, 04:26   #34
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

89D16 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
a1call is offline   Reply With Quote
Old 2017-03-27, 04:30   #35
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

220510 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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))

Thanks in advance.
a1call is offline   Reply With Quote
Old 2017-03-27, 04:31   #36
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

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<best,best=t));best
checks 1 to a million in 5.2 seconds, compared to 91.2 seconds for your version nextPower3RN with the print command stripped out. They gave the same output except on 2 to 7 where yours has a bug. I don't know if that's because of the efficiency of sqrtnint (no need to compute the result to 38 decimals, you can stop once you know which integers it's between) or something else.
CRGreathouse is offline   Reply With Quote
Old 2017-03-27, 04:35   #37
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

32×5×72 Posts
Default

Can you be more specific on the bug?
What value of n gives the wrong result?
a1call is offline   Reply With Quote
Old 2017-03-27, 04:35   #38
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by a1call View Post
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
upperPower = logint(n-1,2)+1
and if n and i are integers which are at least 1, you can use
runningBase = sqrtnint(n-1,i)+1
CRGreathouse is offline   Reply With Quote
Old 2017-03-27, 04:37   #39
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-03-27, 04:39   #40
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-03-27, 05:34   #41
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

32×5×72 Posts
Default

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(theCandidate<smallestPower,
      smallestPower=theCandidate;
      theBase=runningBase;
      theExp=i;
    );
  );
  print("\n",smallestPower," = ",theBase,"^",theExp);
  return(smallestPower);
}
\\Brute-Force
nextPower3(n)={
  m=n;
  if(ispower(n)>2,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
a1call is offline   Reply With Quote
Old 2017-03-27, 14:47   #42
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

7×13×59 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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...
Dr Sardonicus is offline   Reply With Quote
Old 2017-10-03, 02:40   #43
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2·32·233 Posts
Default

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...
EdH is offline   Reply With Quote
Old 2017-10-03, 05:52   #44
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

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(s1<s2,
        s1 += f(n1++)
      ,
        s2 += g(n2++)
      )
    )
  );
}

coincidence(n->if(n>1, 2*n+101, 2704), n->if(n>1, 2*n+13, 2691), 1e6);
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
radius of convergence of a complex power series wildrabbitt Math 3 2016-08-16 08:38
Modification of Fermat's method rdotson Miscellaneous Math 0 2007-07-27 10:32
Elliptic Curve Method factoring - Fermat numbers philmoore Math 131 2006-12-18 06:27
Fermat's factoring method with Gauss's inprovement Carlos Programming 0 2005-09-11 12:50
Convergence of infinite series 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔