Vibap's profile - activity

Hi. The topic of Pell's equation seems to be quite minor among coding sites so I've come to ask for help from professionals at here SageMath community.

https://mathsci.kaist.ac.kr/cms/wp-co...

def solve_pell (N , numTry = 100):
    cf = continued_fraction ( sqrt ( N ))
    for i in range ( numTry ):
        denom = cf.denominator ( i )
        numer = cf.numerator ( i )
        if numer ^2 - N * denom ^2 == 1:
            return numer , denom
    return None , None


solve_pell (21)

The code attached in the last page of the link above works really fine. It finds the fundamental solutions of Pell's equation and I've never seen any other shorter code than the code in the link.

I usually prefer to use the library codes than my self-made codes for the sake of efficiency. However if there aren't any relevant sources, I would have no other choices but make some new codes.

So my questions,

1. Are there any library functions, the libraries that are supported by Sage, regarding finding the non-fundamental solutions of Pell's equation?

2. If not, could you suggest some idea for the code which do the task we desire?

I've tried to make my own code by referring to the algorithm in a document from Wikipedia

however it seems to be using symbolic computations heavily of which I've never tried before. I would be glad for any kind of advice via commens and answers. Thanks.

Generating the non-fundamental solutions of Pell's equation Hi. The topic of Pell's equation seems to be quite minor amo

Generating the non-fundamental solutions of Pell's equation Hi. The topic of Pell's equation seems to be quite minor amo

Generating the non-fundamental solutions of Pell's equation Hi. The topic of Pell's equation seems to be quite minor amo

@JohnPalmieri: So thank you for referring me to the source code!!

@JohnPalmieri: modular function in my codes are slow but it gives an output anyway. However countlength function doesn't

Oh, that seems plausible! I will do experiment myself with your R = Integers(2**127 - 1); R(3)**10000000 method above.

Your source code link is really helpful. Could you help me where I can find a similar source code page with len(str(n))

Your source code link is really helpful. Could you help me where I can find a similar source code page like you've refer

Hi.

Using the same Jupyter Notebook, I've found that identical codes between SageMath and Python turns out that the running time of SageMath shows up much faster than the same code written in Python.

Those codes are as follows.

import timeit

def modular():
    return 3**10000000 % (2**127-1)

def countlength():
    return len(str(3**10000000))



print(timeit.timeit(modular, number=1))
print(timeit.timeit(countlength, number=1))

In SageMath, the running time is less than 1 second for both functions. On the other hand, the running time for "modular' is 5 times slower in Python and for the "countlengh" function, there isn't even an answer from Python.

It makes me curious, what's the magic behind the speed of SageMath?

Recently I'm working on algorithm and coding optimization so any advice from a senior would be grateful.

Thanks.

@MaxAlekseyev: I've tried by myself and indeed. Thank you for so useful tip.

The performance speed of "len(str(n))" method and "a^b % p" method in Sage Hi. Using the same Jupyter Notebook, I've f

Hi. I want to learn how to make some efficient codes manually by referring to verified codes with quality like the ones embedded in Sage.

Is there any way that I can see the detail of the embedded codes like 'next_prime()', 'prime_pi(), 'prime_range()?

Thanks.

Hi. I'm thinking of embedding SageMath Cell into some personal webpage.

Does the calculation speed of SageMath Cell heavily depends on the performance or specs of personal computer?

If so, is there any way that I can improve the calculation speed of SageMath Cell server?

Thanks.

Hi. I understand this question is not contained to SageMath, but I determined to post a question on this forum because I felt this place was the closest to where the experts do exist, regarding math algorithm questions.

If I test and compare the running time of pari.numbpart() and sympy.partition() as the following,

import timeit
import sympy 


def sy(n=10^4):
  sympy.partition(n)

def par(n=10^4):
   pari.numbpart(n)

print('Sympy   \t\t', timeit.timeit(sy, number=1))    
print('PARI    \t\t', timeit.timeit(par, number=1))

I usually see the result as pari.numbpart function running faster. However, I'm not sure whether pari.numbpart is generally faster than sympy.partition.

My question is, what functional approach do pari.numpart and sympy.partition adopt respectively?

There are not many options as long as I know, such as Hardy–Ramanujan–Rademacher and brute force over Young's diagram. If there is someone, I hope ze could let me know what algorithmic approach does each function has taken, and which function is generally faster than the other. Moreover, if possible, I would like to know the complexity time (Big O) of each function.

Thanks.

Thanks. I'm newbie so I didn't know from where I could refer to the documentations! Btw, It seems that Hardy-Ramanujan-

Comparing pari.numbpart() and sympy.partition() Hi. I understand this question is not contained to SageMath, but I deter

I will definitely check until what extent it works. Super thanks!!!

I'm thinking of installing Linux soon. Thank you for introducing the method!!!

Continuing the calculation at Jupyter Notebook on another day I'm running a function at Jupyter Notebook which might cos

Continuing the calculation at Jupyter Notebook on another day I'm running a function at Jupyter Notebook which might cos

wow, so easy! This is why SageMath is the best!

Super Thanks!

Continuing the calculation at Jupyter Notebook in the other day I'm running a function at Jupyter Notebook which might c

The performance speed of SageMath Cell Hi. I'm thinking of embedding SageMath Cell into some personal webpage. Does th

How can I see the detail of embedded codes? Hi. I want to learn how to make some efficient codes manually by referring t