Berechnen phi (k) für 1
https://stackoverflow.com/questions/1024640
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Bei einer großen N, ich brauche durch alle phi (k) zu durchlaufen, so dass 1 Ist es möglich? Wenn ja, wie?
O(N logN) O(N) sein (da die Werte von N rund 10 sein wird 12 )
Lösung
Dies kann mit Speicherkomplexität O (sqrt (N)) und CPU Komplexität O (N * Log (Log (N))) mit einem optimierten Fenster Sieb des Eratosthenes erfolgen, wie weiter unten im Codebeispiel implementiert.
Wie keine Sprache angegeben und wie ich weiß Python nicht, habe ich es in VB.net umgesetzt, jedoch kann ich es in C # konvertieren, wenn Sie das brauchen.
Imports System.Math
Public Class TotientSerialCalculator
'Implements an extremely efficient Serial Totient(phi) calculator '
' This implements an optimized windowed Sieve of Eratosthenes. The'
' window size is set at Sqrt(N) both to optimize collecting and '
' applying all of the Primes below Sqrt(N), and to minimize '
' window-turning overhead. '
' '
' CPU complexity is O( N * Log(Log(N)) ), which is virtually linear.'
' '
' MEM Complexity is O( Sqrt(N) ). '
' '
' This is probalby the ideal combination, as any attempt to further '
'reduce memory will almost certainly result in disproportionate increases'
'in CPU complexity, and vice-versa. '
Structure NumberFactors
Dim UnFactored As Long 'the part of the number that still needs to be factored'
Dim Phi As Long 'the totient value progressively calculated'
' (equals total numbers less than N that are CoPrime to N)'
'MEM = 8 bytes each'
End Structure
Private ReportInterval As Long
Private PrevLast As Long 'the last value in the previous window'
Private FirstValue As Long 'the first value in this windows range'
Private WindowSize As Long
Private LastValue As Long 'the last value in this windows range'
Private NextFirst As Long 'the first value in the next window'
'Array that stores all of the NumberFactors in the current window.'
' this is the primary memory consumption for the class and it'
' is 16 * Sqrt(N) Bytes, which is O(Sqrt(N)).'
Public Numbers() As NumberFactors
' For N=10^12 (1 trilion), this will be 16MB, which should be bearable anywhere.'
'(note that the Primes() array is a secondary memory consumer'
' at O(pi(Sqrt(N)), which will be within 10x of O(Sqrt(N)))'
Public Event EmitTotientPair(ByVal k As Long, ByVal Phi As Long)
'===== The Routine To Call: ========================'
Public Sub EmitTotientPairsToN(ByVal N As Long)
'Routine to Emit Totient pairs {k, Phi(k)} for k = 1 to N'
' 2009-07-14, RBarryYoung, Created.'
Dim i As Long
Dim k As Long 'the current number being factored'
Dim p As Long 'the current prime factor'
'Establish the Window frame:'
' note: WindowSize is the critical value that controls both memory'
' usage and CPU consumption and must be SQRT(N) for it to work optimally.'
WindowSize = Ceiling(Sqrt(CDbl(N)))
ReDim Numbers(0 To WindowSize - 1)
'Initialize the first window:'
MapWindow(1)
Dim IsFirstWindow As Boolean = True
'adjust this to control how often results are show'
ReportInterval = N / 100
'Allocate the primes array to hold the primes list:'
' Only primes <= SQRT(N) are needed for factoring'
' PiMax(X) is a Max estimate of the number of primes <= X'
Dim Primes() As Long, PrimeIndex As Long, NextPrime As Long
'init the primes list and its pointers'
ReDim Primes(0 To PiMax(WindowSize) - 1)
Primes(0) = 2 '"prime" the primes list with the first prime'
NextPrime = 1
'Map (and Remap) the window with Sqrt(N) numbers, Sqrt(N) times to'
' sequentially map all of the numbers <= N.'
Do
'Sieve the primes across the current window'
PrimeIndex = 0
'note: cant use enumerator for the loop below because NextPrime'
' changes during the first window as new primes <= SQRT(N) are accumulated'
Do While PrimeIndex < NextPrime
'get the next prime in the list'
p = Primes(PrimeIndex)
'find the first multiple of (p) in the current window range'
k = PrevLast + p - (PrevLast Mod p)
Do
With Numbers(k - FirstValue)
.UnFactored = .UnFactored \ p 'always works the first time'
.Phi = .Phi * (p - 1) 'Phi = PRODUCT( (Pi-1)*Pi^(Ei-1) )'
'The loop test that follows is probably the central CPU overhead'
' I believe that it is O(N*Log(Log(N)), which is virtually O(N)'
' ( for instance at N = 10^12, Log(Log(N)) = 3.3 )'
Do While (.UnFactored Mod p) = 0
.UnFactored = .UnFactored \ p
.Phi = .Phi * p
Loop
End With
'skip ahead to the next multiple of p: '
'(this is what makes it so fast, never have to try prime factors that dont apply)'
k += p
'repeat until we step out of the current window:'
Loop While k < NextFirst
'if this is the first window, then scan ahead for primes'
If IsFirstWindow Then
For i = Primes(NextPrime - 1) + 1 To p ^ 2 - 1 'the range of possible new primes'
'Dont go beyond the first window'
If i >= WindowSize Then Exit For
If Numbers(i - FirstValue).UnFactored = i Then
'this is a prime less than SQRT(N), so add it to the list.'
Primes(NextPrime) = i
NextPrime += 1
End If
Next
End If
PrimeIndex += 1 'move to the next prime'
Loop
'Now Finish & Emit each one'
For k = FirstValue To LastValue
With Numbers(k - FirstValue)
'Primes larger than Sqrt(N) will not be finished: '
If .UnFactored > 1 Then
'Not done factoring, must be an large prime factor remaining: '
.Phi = .Phi * (.UnFactored - 1)
.UnFactored = 1
End If
'Emit the value pair: (k, Phi(k)) '
EmitPhi(k, .Phi)
End With
Next
're-Map to the next window '
IsFirstWindow = False
MapWindow(NextFirst)
Loop While FirstValue <= N
End Sub
Sub EmitPhi(ByVal k As Long, ByVal Phi As Long)
'just a placeholder for now, that raises an event to the display form'
' periodically for reporting purposes. Change this to do the actual'
' emitting.'
If (k Mod ReportInterval) = 0 Then
RaiseEvent EmitTotientPair(k, Phi)
End If
End Sub
Public Sub MapWindow(ByVal FirstVal As Long)
'Efficiently reset the window so that we do not have to re-allocate it.'
'init all of the boundary values'
FirstValue = FirstVal
PrevLast = FirstValue - 1
NextFirst = FirstValue + WindowSize
LastValue = NextFirst - 1
'Initialize the Numbers prime factor arrays'
Dim i As Long
For i = 0 To WindowSize - 1
With Numbers(i)
.UnFactored = i + FirstValue 'initially equal to the number itself'
.Phi = 1 'starts at mulplicative identity(1)'
End With
Next
End Sub
Function PiMax(ByVal x As Long) As Long
'estimate of pi(n) == {primes <= (n)} that is never less'
' than the actual number of primes. (from P. Dusart, 1999)'
Return (x / Log(x)) * (1.0 + 1.2762 / Log(x))
End Function
End Class
Beachten Sie bei O, dass (N * Log (Log (N))), wird diese Routine jede Zahl an O Faktorisierung (Log (Log (N))) im Durchschnitt, die viel, viel schneller als die schnellste Single-N-Faktorisierung Algorithmen, die von einigen der Antworten hier gelegen. In der Tat, bei N = 10 ^ 12 ist 2400 -mal schneller!
Ich habe diese Routine auf meinem 2GHz Intel Core 2 Notebook getestet und berechnet über 3.000.000 Phi () Werte pro Sekunde. Bei dieser Geschwindigkeit würde es Ihnen etwa 4 Tage dauern, bis 10 ^ 12 Werte zu berechnen. Ich habe getestet es auch für Richtigkeit ohne Fehler zu 100.000.000 auf. Es basiert auf 64-Bit-Integer, so etwas bis zu 2 ^ 63 (10 ^ 19) genau sein soll (obwohl zu langsam für jedermann).
ich auch ein Visual Studio WinForm haben (auch VB.net) zum Laufen / Testen es, dass ich zur Verfügung stellen können, wenn Sie es wollen.
Lassen Sie mich wissen, wenn Sie Fragen haben.
Wie in den Kommentaren gebeten, ich habe unter einer C # Version des Codes hinzugefügt. Doch weil ich zur Zeit bin in der Mitte von einigen anderen Projekten, ich habe keine Zeit, es selbst zu konvertieren, so habe ich eine der Online-VB zu C # Konversionsflächen ( http://www.carlosag.net/tools/codetranslator/ ). So bewusst sein, dass dies automatisch konvertiert, und ich habe keine Zeit gehabt, zu testen, oder überprüfen Sie es mich noch.
using System.Math;
public class TotientSerialCalculator {
// Implements an extremely efficient Serial Totient(phi) calculator '
// This implements an optimized windowed Sieve of Eratosthenes. The'
// window size is set at Sqrt(N) both to optimize collecting and '
// applying all of the Primes below Sqrt(N), and to minimize '
// window-turning overhead. '
// '
// CPU complexity is O( N * Log(Log(N)) ), which is virtually linear.'
// '
// MEM Complexity is O( Sqrt(N) ). '
// '
// This is probalby the ideal combination, as any attempt to further '
// reduce memory will almost certainly result in disproportionate increases'
// in CPU complexity, and vice-versa. '
struct NumberFactors {
private long UnFactored; // the part of the number that still needs to be factored'
private long Phi;
}
private long ReportInterval;
private long PrevLast; // the last value in the previous window'
private long FirstValue; // the first value in this windows range'
private long WindowSize;
private long LastValue; // the last value in this windows range'
private long NextFirst; // the first value in the next window'
// Array that stores all of the NumberFactors in the current window.'
// this is the primary memory consumption for the class and it'
// is 16 * Sqrt(N) Bytes, which is O(Sqrt(N)).'
public NumberFactors[] Numbers;
// For N=10^12 (1 trilion), this will be 16MB, which should be bearable anywhere.'
// (note that the Primes() array is a secondary memory consumer'
// at O(pi(Sqrt(N)), which will be within 10x of O(Sqrt(N)))'
//NOTE: this part looks like it did not convert correctly
public event EventHandler EmitTotientPair;
private long k;
private long Phi;
// ===== The Routine To Call: ========================'
public void EmitTotientPairsToN(long N) {
// Routine to Emit Totient pairs {k, Phi(k)} for k = 1 to N'
// 2009-07-14, RBarryYoung, Created.'
long i;
long k;
// the current number being factored'
long p;
// the current prime factor'
// Establish the Window frame:'
// note: WindowSize is the critical value that controls both memory'
// usage and CPU consumption and must be SQRT(N) for it to work optimally.'
WindowSize = Ceiling(Sqrt(double.Parse(N)));
object Numbers;
this.MapWindow(1);
bool IsFirstWindow = true;
ReportInterval = (N / 100);
// Allocate the primes array to hold the primes list:'
// Only primes <= SQRT(N) are needed for factoring'
// PiMax(X) is a Max estimate of the number of primes <= X'
long[] Primes;
long PrimeIndex;
long NextPrime;
// init the primes list and its pointers'
object Primes;
-1;
Primes[0] = 2;
// "prime" the primes list with the first prime'
NextPrime = 1;
// Map (and Remap) the window with Sqrt(N) numbers, Sqrt(N) times to'
// sequentially map all of the numbers <= N.'
for (
; (FirstValue <= N);
) {
PrimeIndex = 0;
// note: cant use enumerator for the loop below because NextPrime'
// changes during the first window as new primes <= SQRT(N) are accumulated'
while ((PrimeIndex < NextPrime)) {
// get the next prime in the list'
p = Primes[PrimeIndex];
// find the first multiple of (p) in the current window range'
k = (PrevLast
+ (p
- (PrevLast % p)));
for (
; (k < NextFirst);
) {
// With...
UnFactored;
p;
// always works the first time'
(Phi
* (p - 1));
while (// TODO: Warning!!!! NULL EXPRESSION DETECTED...
) {
(UnFactored % p);
UnFactored;
(Phi * p);
}
// skip ahead to the next multiple of p: '
// (this is what makes it so fast, never have to try prime factors that dont apply)'
k = (k + p);
// repeat until we step out of the current window:'
}
// if this is the first window, then scan ahead for primes'
if (IsFirstWindow) {
for (i = (Primes[(NextPrime - 1)] + 1); (i
<= (p | (2 - 1))); i++) {
// the range of possible new primes'
// TODO: Warning!!! The operator should be an XOR ^ instead of an OR, but not available in CodeDOM
// Dont go beyond the first window'
if ((i >= WindowSize)) {
break;
}
if ((Numbers[(i - FirstValue)].UnFactored == i)) {
// this is a prime less than SQRT(N), so add it to the list.'
Primes[NextPrime] = i;
NextPrime++;
}
}
}
PrimeIndex++;
// move to the next prime'
}
// Now Finish & Emit each one'
for (k = FirstValue; (k <= LastValue); k++) {
// With...
// Primes larger than Sqrt(N) will not be finished: '
if ((Numbers[(k - FirstValue)].UnFactored > 1)) {
// Not done factoring, must be an large prime factor remaining: '
(Numbers[(k - FirstValue)].Phi * (Numbers[(k - FirstValue)].UnFactored - 1).UnFactored) = 1;
Numbers[(k - FirstValue)].Phi = 1;
}
// Emit the value pair: (k, Phi(k)) '
this.EmitPhi(k, Numbers[(k - FirstValue)].Phi);
}
// re-Map to the next window '
IsFirstWindow = false;
this.MapWindow(NextFirst);
}
}
void EmitPhi(long k, long Phi) {
// just a placeholder for now, that raises an event to the display form'
// periodically for reporting purposes. Change this to do the actual'
// emitting.'
if (((k % ReportInterval)
== 0)) {
EmitTotientPair(k, Phi);
}
}
public void MapWindow(long FirstVal) {
// Efficiently reset the window so that we do not have to re-allocate it.'
// init all of the boundary values'
FirstValue = FirstVal;
PrevLast = (FirstValue - 1);
NextFirst = (FirstValue + WindowSize);
LastValue = (NextFirst - 1);
// Initialize the Numbers prime factor arrays'
long i;
for (i = 0; (i
<= (WindowSize - 1)); i++) {
// With...
// initially equal to the number itself'
Phi = 1;
// starts at mulplicative identity(1)'
}
}
long PiMax(long x) {
// estimate of pi(n) == {primes <= (n)} that is never less'
// than the actual number of primes. (from P. Dusart, 1999)'
return ((x / Log(x)) * (1 + (1.2762 / Log(x))));
}
}
Andere Tipps
Niemand hat einen schnelleren Weg zu berechnen phi (k) (aka gefunden, Eulersche Phi-Funktion ) als indem man zuerst die Primfaktoren von k zu finden. Die besten Mathematiker der Welt haben seit 1977 viele CPU-Zyklen auf das Problem geworfen, da ein schneller Weg zu finden, um dieses Problem zu lösen, wäre eine Schwäche in der RSA public-Key-Algorithmus . (Sowohl der öffentliche und der private Schlüssel in RSA berechnet auf Basis von phi (n), wobei n das Produkt zweier großer Primzahlen ist.)
Die Berechnung von phi (k) muss getan werden, um die Primfaktorzerlegung von k verwendet, die der einzige vernünftige Weg ist, es zu tun. Wenn Sie eine Auffrischung, dass benötigen, wikipedia trägt die Formel .
Wenn Sie nun alle Primfaktoren jeder Zahl zwischen 1 und einem großen N berechnen haben, werden Sie an Altersschwäche sterben, bevor sie irgendein Ergebnis zu sehen, also würde ich den anderen Weg gehen um, also bauen alle Zahlen unter N , ihre möglichen Primfaktoren verwenden, dh alle Primzahlen kleiner oder gleich N ist.
Ihr Problem daher wird ähnlich sein, alle Divisoren einer Zahl Berechnung, nur Sie wissen nicht, was die maximale Anzahl von Malen ist, dass Sie vorher eine gewisse Primzahl in der Faktorisierung finden. Tweaking einen Iterator ursprünglich von Tim Peters auf der Python-Liste geschrieben (etwas Ich habe gebloggt ...) um die Totientenfunktion, eine mögliche Implementierung in Python, die k ergibt, phi (k) -Paare sein könnte wie folgt:
def composites(factors, N) :
"""
Generates all number-totient pairs below N, unordered, from the prime factors.
"""
ps = sorted(set(factors))
omega = len(ps)
def rec_gen(n = 0) :
if n == omega :
yield (1,1)
else :
pows = [(1,1)]
val = ps[n]
while val <= N :
pows += [(val, val - pows[-1][0])]
val *= ps[n]
for q, phi_q in rec_gen(n + 1) :
for p, phi_p in pows :
if p * q > N :
break
else :
yield p * q, phi_p * phi_q
for p in rec_gen() :
yield p
Wenn Sie auf die Berechnung alle Primfaktoren unter N Hilfe benötigen, habe ich auch darüber gebloggt ... Denken sie daran, auch wenn das Rechen alle Primzahlen unter 10 12 in sich eine ganz bemerkenswerte Leistung ist .. .
Ist das von Project Euler 245? Ich erinnere mich an diese Frage, und ich habe auf sie aufgegeben.
Der schnellste Weg, ich für die Berechnung totient fand, war die Primfaktoren (p-1) zusammen zu multiplizieren, da k keine wiederholten Faktoren hat (was nie der Fall war, wenn ich das Problem richtig erinnere).
So Faktoren für die Berechnung, wäre es wahrscheinlich am besten verwenden gmpy.next_prime oder pyecm (Elliptic Curve Faktorisierung).
Sie können auch die Primfaktoren Sieb als Jaime vermuten lässt. Bei Zahlen bis zu 10 12 ist der maximale Primfaktors unter 1 Million, das angemessen sein sollte.
Wenn Sie Faktorisierungen memoize, könnte es Ihre Phi-Funktion noch mehr beschleunigen.
Für diese Art von Problemen, die ich bin mit einem Iterator, der für jede ganze Zahl zurückgibt m
Mit einer Liste von Primzahlen
Dieses Verfahren hat die Komplexität O ( N log (log ( N ))) unter der Annahme, dass alle Operationen einschließlich Listenoperationen O nehmen (1). Der Speicherbedarf ist O (sqrt ( N )).
Es ist leider, einige konstanten Overhead hier, daher wurde ich für einen eleganteren Weg suchen, um die Werte phi (n) zu erzeugen, aber so, denn ich habe nicht erfolgreich gewesen.
Hier ist ein effizienter Python-Generator. Der Nachteil ist, dass es nicht die Ergebnisse, um nicht zu ergeben. Es basiert auf https://stackoverflow.com/a/10110008/412529 .
Speicherkomplexität: O (log (N)), da es nur eine Liste von Primfaktoren für eine einzelne Zahl zu einem Zeitpunkt, zu speichern hat.
CPU Komplexität ist nur knapp superlinear, so etwas wie O (N log N log).
def totientsbelow(N):
allprimes = primesbelow(N+1)
def rec(n, partialtot=1, min_p = 0):
for p in allprimes:
if p > n:
break
# avoid double solutions such as (6, [2,3]), and (6, [3,2])
if p < min_p: continue
yield (p, p-1, [p])
for t, tot2, r in rec(n//p, partialtot, min_p = p): # uses integer division
yield (t*p, tot2 * p if p == r[0] else tot2 * (p-1), [p] + r)
for n, t, factors in rec(N):
yield (n, t)
Ich glaube, Sie in die andere Richtung gehen können, um. Statt Faktorisierung eine ganze Zahl k phi zu erhalten (k) können Sie alle Zahlen von 1 bis N von Primzahlen zu erzeugen versuchen und schnell phi (k) zu erhalten. Zum Beispiel, wenn P n wird die maximale Primzahl, die kleiner als N ist, können Sie erzeugen alle ganzen Zahlen weniger als N von
P 1 i 1 * P 2 i 2 * ... * P n i n , wobei jeder i j läuft von 0 bis [ log (N) / log (P j )] ([] ist der Boden-Funktion).
Auf diese Weise können Sie phi (k) schnell wihout teuer Primfaktorzerlegung bekommen und immer noch zwischen 1 und N durch alle k iterieren (nicht in Ordnung, aber ich glaube, Sie nicht über Auftrag egal).
Sieb der totients zu n :
(define (totients n)
(let ((tots (make-vector (+ n 1))))
(do ((i 0 (+ i 1))) ((< n i))
(vector-set! tots i i))
(do ((i 2 (+ i 1))) ((< n i) tots)
(when (= i (vector-ref tots i))
(vector-set! tots i (- i 1))
(do ((j (+ i i) (+ i j))) ((< n j))
(vector-set! tots j
(* (vector-ref tots j) (- 1 (/ i)))))))))
Dieses faktorisiert N = PQ, wobei P & Q prim sind.
funktioniert ganz gut, in Elixir oder Erlang.
Sie können versuchen, verschiedene Generatoren für Ihre Pseudo-Zufallsfolge. x*x + 1 wird häufig verwendet.
Diese Zeile: defp f0(x, n), do: rem((x * x) + 1, n)
Weitere mögliche Verbesserungspunkte: bessere oder alternative gcd rem und abs Funktionen
defmodule Factorizer do
def factorize(n) do
t = System.system_time
x = pollard(n, 2_000_000, 2_000_000)
y = div(n, x)
p = min(x, y)
q = max(x, y)
t = System.system_time - t
IO.puts "
Factorized #{n}: into [#{p} , #{q}] in #{t} μs
"
{p, q}
end
defp gcd(a,0), do: a
defp gcd(a,b), do: gcd(b,rem(a,b))
defp pollard(n, a, b) do
a = f0(a, n)
b = f0(f0(b, n), n)
p = gcd(abs(b - a), n)
case p > 1 do
true -> p
false -> pollard(n, a, b)
end
end
defp f0(x, n), do: rem((x * x) + 1, n)
end
