Power 2

[cheesehead]

"Trial factoring" is not the only, and may not be the most common, name for this method outside the GIMPS community.

Wolfram Mathworld (http://mathworld.wolfram.com/) lists "Direct Search Factorization" (http://mathworld.wolfram.com/DirectS...orization.html) and "Trial Division" (http://mathworld.wolfram.com/TrialDivision.html) as names for the method we know as Trial Factoring.

[JohnFullspeed]

If you want to factorize a number n you have to divide the n by all the primes smaller than √n
So if you compute the primes until 32 bits (200 000 000):(1 second with YAKU )you can factorize 10^20.
directly.

After it's easy
Let Prime be the list of prime until 32bits
and FP the list of the primes factors

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

It is today the faster method : Let m be the time is how div my computer do in 1 second and if n is prime and 10^19 you need 200 000 000 / m secondes
the problem is just the memory configuration; the Prime list is 770 Mo so you need 1Giga.
but today all computers have more than 1 G of RAM
and it easy to use less.
John

[Mini-Geek]

Originally Posted by JohnFullspeed

If you want to factorize a number n you have to divide the n by all the primes smaller than √n

http://en.wikipedia.org/wiki/Integer_factorization

[R. Gerbicz]

Originally Posted by JohnFullspeed

If you want to factorize a number n you have to divide the n by all the primes smaller than √n
...(1 second with YAKU )

Your method is broken for n=4.
What is YAKU?

[JohnFullspeed]

The method is exactly given by WiKi
for big factor we use a quadratic Sieve for small
factors division


A question

You use 2 power so how do you ytest tha a value n is a 2 power?
for example 5623852325444865747416 2 power or no?

Thanks

john

[science_man_88]

Originally Posted by JohnFullspeed

The method is exactly given by WiKi
for big factor we use a quadratic Sieve for small
factors division


A question

You use 2 power so how do you ytest tha a value n is a 2 power?
for example 5,623,852,325,444,865,747,416 2 power or no?

Thanks

john

well one note the 6 on the end it can tell me 2 things one it's divisible by 2, and two if it is a power of 2 it's 2^x where x of the form 4y because the end digits go 2,4,8,6,2,4,8,6. the length tells me it would have to be about 72 or 73, 72 is divisible by 4 so it would have to be that if it was. Of course I'm crap at this stuff. also you may realize that 72 is divisible by 6 which means if you sum the digits until you get a number under 9 you'll get 5 if it can be. adding up the digits that way we get 2 so it's not 2^72 and therefore it isn't a power of 2 as we've proven it could only be 2^72 .

[ldesnogu]

Originally Posted by JohnFullspeed

You use 2 power so how do you ytest tha a value n is a 2 power?
for example 5623852325444865747416 2 power or no?

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

[JohnFullspeed]

Originally Posted by ldesnogu

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

Thanks to the 2 Canadians. I use an other way but wih ASM so this version is better:I adopt

If BSR(n) = BSL(n)

a 2 power have only one bit set to one so if the offset rigth of the first bit is the same than the left thatmean that you have 1 bit set to 1
More : BSL or BSR give you the power of 2 if you need itt


The version of science_man_88 is interesting It shows the difference inbto a human logc and the computer and whyy mathématician need computer specialist

You say that to know if n is a multiple of 6 the sum of the digitsmust be 5
It'Strue and easy to computefor a humman but for the computer is't very long.
because we work in Base 1 and the computer in BASE 2
so if you fave 123 iis easy to compute 1+2+3=6
But the compuyer have 1111011 it s more difficult to find 1,2,3
so he need to change is base to convert 1111011 in 123 (itoa)
The change is long. It many more faster for the computer to compute the modulo 6 . The mod will 0 is n is a multiple

The computer do if N mod 6=0

The 'human commputer' do
s== atoi(n)
l:= length(s);
G:=0
for i:=1 to L do
G:=G+(S(i)-48);
If G=5... i

the human directly compute 1+2+3 no timùe and compare the result with 5

In fact the speed method is to make the didv 123 /6 and the computer is the speeder. But never your computer understand what it does and knows why. Only thr humman do that. A computer never find how to solve a proble . It just compute always more quickly

John

[ldesnogu]

Originally Posted by JohnFullspeed

Thanks to the 2 Canadians. I use an other way but wih ASM so this version is better:I adopt

If BSR(n) = BSL(n)

a 2 power have only one bit set to one so if the offset rigth of the first bit is the same than the left thatmean that you have 1 bit set to 1

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.

[JohnFullspeed]

It 's always good to learn
john

[R.D. Silverman]

Originally Posted by JohnFullspeed

[SIZE=4]If you want to factorize a number n you have to divide the n by all the primes smaller than √n

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.