Power 2

[R.D. Silverman]

Originally Posted by ldesnogu

Did you mean Intel BSF/BSR? If so get ready for being disappointed as these two instruction implementation performance vary wildly depending on the CPU.

And of course, if the number being tested is multi-precision
other work must be done as well.

[ewmayer]

Originally Posted by ldesnogu

For n non zero, n is a power of two iff n & (n-1) = 0

I was going to suggest testing (n >> trailz(n)) == 1, but your method is quicker.

[R.D. Silverman]

Originally Posted by ewmayer

I was going to suggest testing (n >> trailz(n)) == 1, but your method is quicker.

If n is very large the fastest method of all might be just a fast evaluation
of log_2(n) in floating point just using the most significant limb. If
log_2(n) is very close to floor(log_2(n)) one then switches to another
method.

I assume that n is multi-precision. (typical for this forum)

[Christenson]

Originally Posted by R.D. Silverman

If n is very large the fastest method of all might be just a fast evaluation
of log_2(n) in floating point just using the most significant limb. If
log_2(n) is very close to floor(log_2(n)) one then switches to another
method.

I assume that n is multi-precision. (typical for this forum)

You should also assume it's being represented in binary form....this won't work well if its stored as decimals, or some other representation, like M(43112609), or 3^2517 + 41^3258, or FFT(x).

[JohnFullspeed]

Originally Posted by R.D. Silverman

If you ever bothered to do even minimal reading about factoring methods,
you would quickly learn that you do NOT "have to divide the n by all the primes smaller than √n".

Indeed, algorithms exist that do not do ANY division.

Further, even when using trial division you do not have to divide
by all the primes up to . You divide by 2,3,5, ..... p,
reducing n by each factor found until p^2 is greater than the remaining
cofactor. Trial division quits when the cofactor is prime. Only
when does one divide all the way to and this case is handled
in only 1 iteration by Fermat's method
(which requires no division at all!)

Do us all a favor. Drop your arrogance and go away until you have
done some background reading about number theory in general, and
computational number theory in particular. Every time you talk, you
say something grossly wrong.

Please what is wrong in my method to see if it's a power of two
Not for me but the readers...(They can jointt you to say thaat I'm bad)


You dont have read the code

R:=  √n
I:=1;
C:=0;
repeat
 while n   mod  Prime[i]=0 do
begin
   C:=  C+1;
   PF[C]:= Prime[i];  // save thr factor
   n:- n div  Prime[i];  //  new value to factorize
  R:=  √n;                //  new limit for searching
end
I:= I+1;
until Prime[i]> R

Prime is the list of prim even except 2
after I reduce n at each factor find
and i compute the new limit ( perhaps it exist a faster way t compute the

For the DIIV it's slow for you but not for me you need 100 cycles (docc Intel) me ONE so div,add,* is equal 1 cycle:it's calla RISC processor: you want that explain you why all calculators have RISC

we can for example ask to someone to compute the product of X primes and we factorize it...> 1000 digits
Or if you prefer we compute n with the number of factor random and tthe value of the prime factors

The number will have many digits but it's not a problem for you
Every one could see that I must return to school or yoo




Do me aa favor continue to do not answer on my tropics :I don't have to sort the answwer

[ldesnogu]

Originally Posted by R.D. Silverman

If n is very large the fastest method of all might be just a fast evaluation
of log_2(n) in floating point just using the most significant limb. If
log_2(n) is very close to floor(log_2(n)) one then switches to another
method.

I assume that n is multi-precision. (typical for this forum)

Assuming a power of two base, I'd expect the fastest implementation to be to first check the most significant limb is a power of two, using l[n-1] & (l[n -1] - 1) = 0, then check all the other limbs are zero, with early exit if any test fails. Of course the 0 case is special

[JohnFullspeed]

I say thatthe division method was the speeder way to factorize

I get Fermat mmethod like answer
Is't ttue the method is faster but IT SEEMS that we cannot use it in quadratic sieve because in a quadratic sieve we don't use all the primes but a base of prime

But it's true the Fermat method is speeder than the method I indicate( and I still alive) Now I find the speeder method to detect a perfect square

John

[R.D. Silverman]

Originally Posted by ldesnogu

Assuming a power of two base, I'd expect the fastest implementation to be to first check the most significant limb is a power of two, using l[n-1] & (l[n -1] - 1) = 0, then check all the other limbs are zero, with early exit if any test fails. Of course the 0 case is special

Yes, but my method avoids checking all of the other limbs. There
could be a lot of them. The cost tradeoff is that computing a log
(even just a single one) is relatively expensive.

[R.D. Silverman]

Originally Posted by Christenson

You should also assume it's being represented in binary form....this won't work well if its stored as decimals, or some other representation, like M(43112609), or 3^2517 + 41^3258, or FFT(x).

Computing the log is independent of representation.

[R.D. Silverman]

Originally Posted by JohnFullspeed

Do me aa favor continue to do not answer on my tropics :I don't have to sort the answwer

Sure. I'll do you this favor. But only in return for a favor on your part.
Stop all of your posting until you can supply some evidence that you have
studied some computational number theory.

[fivemack]

Originally Posted by R.D. Silverman

Yes, but my method avoids checking all of the other limbs. There
could be a lot of them. The cost tradeoff is that computing a log
(even just a single one) is relatively expensive.

Your method requires checking all (OK, some) of the other limbs if the log of the first limb (which will surely be computed by finding the first set bit, dividing by 2^that, then fitting some bit of power series) is close to a power of two; his method requires checking all (OK, some) of the other limbs if the first limb has only one set bit.

I am reasonably confident that computing a log is more expensive than checking for one set bit.