Pollard rho czynniki pierwsze.

narnano
2012-02-23 13:40
narnano
0

Chcialbym sie dowiedziec jaki algorytm bedzie wstanie jak najszybciej rozlozyc liczbe typu "long long" na czynniki pierwsze.Troche poczytalem na necie i chyba jest to algorytm Pollard rho. Czy to prawda??

Poniżej pseudokod. Czy ktos pomoze mi go napisac w c++?

function pollardRho(N)
# Initial values x(i) and x(2*i) for i = 0.
xi := 2
x2i := 2
do
# Find x(i+1) and x(2*(i+1))
xiPrime := xi ^ 2 + 1
x2iPrime := (x2i ^ 2 + 1) ^ 2 + 1
# Increment i: change our running values for x(i), x(2*i).
xi := xiPrime % N
x2i := x2iPrime % N
s := gcd(xi - x2i, N)
if s <> 1 and s <> N then
return s, N/s
end if
end do
end function

Pozostało 580 znaków

narnano
2012-02-23 14:49
narnano
0

Naszła mnie teraz taka myśl:
A jakby tak wcześniej obliczyć sobie liczby pierwsze.
A potem tylko sprawdzać czy dana liczba pierwsza dzieli się bez reszty to jest czynnikiem tej liczby.
Czy taka opcja dawałaby dobre wyniki? I czy dużo by zajmowałoby miejsca obliczenie liczb pierwszych do 10 cyfr?

Pozostało 580 znaków

jo
2012-02-23 14:54
jo
0
narnano napisał(a)

potem tylko sprawdzać czy dana liczba pierwsza dzieli się bez reszty to jest czynnikiem tej liczby.

Jeśli jest liczbą pierwszą to trudno żeby dzieliła się bez reszty przez jakąkolwiek inna liczbę niż samą siebie i jedynkę :]

Pozostało 580 znaków

narnano
2012-02-23 14:57
narnano
0

Moze cos pokreciłem.
Chce wyznaczyc w jak najszybszy sposob czynniki pierwsze podanej przezemnie liczby. Z tym ze bd to duza liczba ok 10cyfrowa.
Czy wyliczenie najpierw liczb pierwszych przyspieszyloby proces szukania czynnikow ?

Pozostało 580 znaków

2012-02-23 14:59
Moderator

Rejestracja: 16 lat temu

Ostatnio: 19 minut temu

0

Niewątpliwie tak, bo dzieliłbyś swoją liczbę tylko przez liczby pierwsze ;]


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

narnano
2012-02-23 15:02
narnano
0

Tylko jak to teraz zrealizowac?
zapisac kazdą liczbe pierwsza w jednej linijce pliku txt.
A potem w programie czytac linia po lini i sprawdzac warunek? czy jest na to lepszy sposob?

Pozostało 580 znaków

ihoo
2012-02-23 15:25
ihoo
0
narnano napisał(a)

Czy taka opcja dawałaby dobre wyniki? I czy dużo by zajmowałoby miejsca obliczenie liczb pierwszych do 10 cyfr?
liczby pierwsze do milliarda zajmowałby troszkę ponad 60 MB.

Pozostało 580 znaków

narnano
2012-02-23 15:27
narnano
0

Taki rozmiar mi odpowiada. Tylko czy przy sprawdzaniu wczytywac te liczby do tablicy i dopiero sprawdzac czy czytac je linijka po linijce i sprawdzac ?
ktore rozwiazanie bd najszybsze?

Pozostało 580 znaków

2012-02-23 15:30
Moderator

Rejestracja: 16 lat temu

Ostatnio: 19 minut temu

0

Operacje I/O są ekstremalnie wolne. Jak będziesz czytał to z pliku linijka po linijce (i kompilator nie uratuje cię buforowaniem) to szybciej byłoby liczyć to na bieżąco ;]


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2012-02-23 16:00

Rejestracja: 8 lat temu

Ostatnio: 6 lat temu

0

Po pierwsze wystarczą Ci tylko liczby pierwsze do sqrt(max). Po drugie jeżeli program ma wyznaczyć tylko rozkład jednej liczby (a nie dużego zbioru) to wystarczy, że będziesz dzielił przez kolejne liczby mniejsze niż pierwiastek z szukanej liczby. 10^5.5 dzieleń to nie jest wcale tak dużo (można dodać mnożenie, żeby szybciej wyjść z pętli).

edytowany 1x, ostatnio: Zjarek, 2012-02-23 16:01

Pozostało 580 znaków

Nuszja
2012-03-30 15:45
Nuszja
0

Ekstremalny jest algorytm zmiany systemow liczbowych.
Dokladniejsze informacje o algorytmie oraz sposobie konwersji jest na
matformac.blogspot.com
Algorytm sprawdzil mi, ze liczba bliska wielkosci slowa maszynowego jest pierwsza w czasie krotszym niz milisekunda.

Pozostało 580 znaków

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0