#16880: previous_prime, previous_prime_power, next_prime_power
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.7
Component: number theory | Resolution:
Keywords: | Merged in:
Authors: Vincent Delecroix | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/16880 | 1e0956157ef8f49bc19eb145dc60589f8e59587a
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by vdelecroix):
* status: needs_work => needs_review
Comment:
Replying to [comment:20 jdemeyer]:
> 4. Another algorithmic comment for `next_prime_power` (an analogous
comment holds for `previous_prime_power`): instead of computing the next
power of 2 and doing
> {{{
> while mpz_cmp(m.value, n.value) == 1:
> }}}
> I would instead check if `mpz_sizeinbase(n.value, 2)` increases during
the loop. In that case, we know that we skipped a power of 2.
I used `mpz_tstbit` instead. Should be the fastest.
Potential micro optimization that would need to use `mpn_*` functions
- the call to `mpz_sizeinbase` can be replaced by
`mpn_count_leading_zeros` and some arithmetic
- we can avoid a useless bit shift in `mpz_tstbit` by only considering
the `&` with the most significant limb. Moreover, the allocation of the
limbs will not change inside the loop. So we can already use the good
pointer to the concerned limb.
I think this is too much for a naive algorithm...
--
Ticket URL: <http://trac.sagemath.org/ticket/16880#comment:23>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
