I don't know of any algorithms to find the radical of an integer quickly (indeed I believe there aren't any) but here are some ideas I have.
First, if you're dabbling in cython, try making your primessq into a cdef long*. This should speed things up significantly. If your calling from other cython code, you could make int_has_small_square_divisor into a cdef function as well. You are doing the work of division twice, you might want to consider using mpz_fdiv_q_ui (and throwing away the resulting q if the remainder is non-zero). This depends on how rare square divisors are, as mpz_divisible_ui_p may be a bit faster (I don't know though). If p is small enough, it might fit into a long long, even on a 32-bit machine. - Robert On Oct 9, 2007, at 10:52 PM, John Voight wrote: > I decided on something like this: > > ----- > > cimport sage.rings.integer > > primessq = [4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, > 1681, 1849, > 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, > 7921, 9409] > len_primes = 25 > > def int_has_small_square_divisor(sage.rings.integer.Integer d): > cdef int i, asq = 1 > > for i from 0 <= i < len_primes: > while mpz_divisible_ui_p(d.value, primessq[i]): > asq *= primessq[i] > mpz_divexact_ui(d.value, d.value, primessq[i]) > return asq > > ----- > > Comments? > > JV > > > --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
