Posts: 31

Threads: 4

Joined: Oct 2005

Quote:@ Whodat: Go to your profile and check the "Always allow BBCode:", make sure that is selected to "Yes".... Then the BB code will work and you wont have to back it out... :wink:

Thanks. Did that and I think I'm getting the hang of it.

Posts: 2,404

Threads: 153

Joined: Jan 2005

Your welcome... :wink:

Kevin (

x.t.r.GRAPHICS)

Posts: 1,407

Threads: 117

Joined: Dec 2002

Quote:Nice, methinks you could probably create some sort of string with the values of the first X primes to speed it up too.. or something.

Aga: Probably calculating that primes would be slower than doing the tests, unless that primes were hardwired with the program.

Notice that removing the multiples of 3 and 2 avoids 2/3 of the tests (IIRC), further optimizations would give only minor gains.

Antoni

Posts: 17

Threads: 0

Joined: May 2005

Code:

`DEFLNG N`

INPUT "number to be factorized"; n

DIM a(22000) AS STRING * 1

FOR J = 2 TO 110

IF a(J) <> CHR$(0) GOTO 10

IST = J + J - 1

FOR i = J + IST TO 22000 STEP IST

a(i) = CHR$(1)

NEXT i

10 NEXT J

i = 1

WHILE n MOD 2 = 0

PRINT "2 ";

n = n \ 2

WEND

110 WHILE i < 22000

i = i + 1

IF a(i) = CHR$(0) AND n MOD (i + i - 1) = 0 THEN

PRINT i + i - 1;

jq = jq * (i + i - 1)

n = n \ (i + i - 1)

i = 1

END IF

WEND

IF n > 1 THEN PRINT n

Posts: 1,407

Threads: 117

Joined: Dec 2002

I have enhanced my post by using DOUBLEs to be able to factorize values up to 5e15. By using ffix it declares 4999999999999997 prime in 12 seconds in my computer ..I hope it's really prime...

EDITED: It is. You can check your factorizations here

http://www.alpertron.com.ar/ECM.HTM
Code:

`declare sub ffix()`

declare sub checkf(k#)

dim shared x#,C#

ffix

do

print

INPUT "enter a number to factorize[0 to end] : ", x#

if x#<=0 or x#>5E15 then exit do

t!=timer:c#=1

PRINT "the prime factors are:";

checkf(2#)

checkf(3#)

a#=2

k# = 3 + a#

WHILE K# <= sqr(x#)

checkf(k#)

k# = k# + a#

a#=6#-a#

WEND

if x#>1 then print x#;:c#=c#*x#

print: PRINT "Ended in ";timer-t!;" seconds. Product of all factors: "; C#

loop

sleep

sub checkf(k#)

do

x1# = x# / k#

if x1#-int(x1#)>1e-15 then exit do

PRINT k#;

C#=C#*K#

x#=x1#

loop

end sub

Antoni

Posts: 500

Threads: 7

Joined: Jun 2005

Quote:I have enhanced my post by using DOUBLEs to be able to factorize values up to 5e15. By using ffix it declares 4999999999999997 prime in 12 seconds in my computer ..I hope it's really prime...

EDITED: It is. You can check your factorizations here http://www.alpertron.com.ar/ECM.HTM

Code:

`declare sub ffix()`

declare sub checkf(k#)

dim shared x#,C#

ffix

do

print

INPUT "enter a number to factorize[0 to end] : ", x#

if x#<=0 or x#>5E15 then exit do

t!=timer:c#=1

PRINT "the prime factors are:";

checkf(2#)

checkf(3#)

a#=2

k# = 3 + a#

WHILE K# <= sqr(x#)

checkf(k#)

k# = k# + a#

a#=6#-a#

WEND

if x#>1 then print x#;:c#=c#*x#

print: PRINT "Ended in ";timer-t!;" seconds. Product of all factors: "; C#

loop

sleep

sub checkf(k#)

do

x1# = x# / k#

if x1#-int(x1#)>1e-15 then exit do

PRINT k#;

C#=C#*K#

x#=x1#

loop

end sub

I hope no round-off errors are experienced with those floating-point numbers. :roll:

974277320612072617420666C61696C21 (Hexadecimal for those who don't know)

Posts: 17

Threads: 0

Joined: May 2005

You've got a fast computer there Antoni. On my computer it took 143 sec (with FFIX) and without it (FFIX) it still hasn't finished.

Is there the same problem (bug?) with integer arithmetic. I say this because double with FFIX seems to run faster than long integer.

Posts: 1,407

Threads: 117

Joined: Dec 2002

A LONG will not allow you to factorize 4999999999999997. It should give you an overflow....And in modern computers, double can be faster than a long calculated in 16 bits mode.

There are no rounding errors I know of: the tests I ran gave the same result than Mr Alpert site. However I have not tested all integers from 1 to 1e15 using both methods

If you find some wrong result, please let me know.

Antoni

Posts: 17

Threads: 0

Joined: May 2005

Actually you can use long because the factors that need to be calculated never exceed long integer.

Posts: 1,407

Threads: 117

Joined: Dec 2002

You're right, but your way is slower:

If the number to factorize is double and the factors are long, factors must be converted to double every time they are operated or compared with the number. The results of the operations are double so they must be converted back if they are stored in a long...

Antoni