Вычисление phi (k) для 1 <k <N
Я автор Docker.
Краткий ответ: если вы хотите управлять машинами, вам следует использовать Vagrant. А если вы хотите создавать и запускать среды приложений, вам следует использовать Docker.
Vagrant - это инструмент для управления виртуальными машинами. Docker - это инструмент для создания и развертывания приложений путем упаковки их в легкие контейнеры. Контейнер может содержать практически любой программный компонент вместе со своими зависимостями (исполняемые файлы, библиотеки, файлы конфигурации и т. Д.) И выполнять его в гарантированной и воспроизводимой среде выполнения. Это позволяет очень просто создать приложение и развернуть его где угодно - на ноутбуке для тестирования, затем на разных серверах для оперативного развертывания и т. Д.
Это распространенное заблуждение, что вы можете использовать Docker только в Linux. Это неверно; Вы также можете установить Docker на Mac и Windows. При установке на Mac Docker связывает крошечную виртуальную машину Linux (25 МБ на диске!), Которая действует как оболочка для вашего контейнера. После установки это полностью прозрачно; вы можете использовать командную строку Docker точно таким же образом. Это дает вам лучшее из обоих миров: вы можете тестировать и разрабатывать свое приложение с использованием контейнеров, которые очень легки, просты в тестировании и легко перемещаются (см., Например, https://hub.docker.com . ] для совместного использования многократно используемых контейнеров с сообществом Docker), и вам не нужно беспокоиться о мельчайших подробностях управления виртуальными машинами, которые в любом случае являются лишь средством достижения цели.
Теоретически возможно использовать Vagrant в качестве уровня абстракции для Docker. Я рекомендую против этого по двум причинам:
-
Во-первых, Вагрант не является хорошей абстракцией для Докера. Vagrant был разработан для управления виртуальными машинами. Docker был разработан для управления временем выполнения приложения. Это означает, что Docker по своему замыслу может взаимодействовать с приложением более богатыми способами и имеет больше информации о времени выполнения приложения. Примитивы в Docker - это процессы, потоки журналов, переменные среды и сетевые связи между компонентами. Примитивы в Vagrant - это машины, блочные устройства и ssh-ключи. Vagrant просто находится ниже в стеке, и единственный способ, которым он может взаимодействовать с контейнером, - притворяться, что это просто еще один тип машины, которую вы можете «загружать» и «входить в систему». Так что, конечно, вы можете напечатать «vagrant up» с помощью плагина Docker, и что-то очень красивое произойдет. Является ли это заменой всей широте возможностей Docker? Попробуйте родной Docker на пару дней и убедитесь сами:)
-
Во-вторых, аргумент блокировки. «Если вы используете Vagrant в качестве абстракции, вы не будете заблокированы в Docker!». С точки зрения Vagrant, который предназначен для управления машинами, это имеет смысл: не являются ли контейнеры просто еще одним видом машины? Так же, как Amazon EC2 и VMware, мы должны быть осторожны, чтобы не связывать наши инструменты обеспечения с каким-либо конкретным поставщиком! Это создаст блокировку - лучше абстрагироваться от Vagrant. За исключением того, что это полностью упускает из виду Docker. Докер не предоставляет машины; оно оборачивает ваше приложение в легкую переносимую среду выполнения, которую можно отбросить куда угодно.
То, какое время выполнения вы выбираете для своего приложения, не имеет никакого отношения к тому, как вы готовите свои машины! Например, довольно часто можно развертывать приложения на компьютерах, которые предоставлены кем-то другим (например, экземпляр EC2, развернутый вашим системным администратором, возможно, с помощью Vagrant), или на чистых машинах, которые Vagrant не может предоставить вообще. И наоборот, вы можете использовать Vagrant для предоставления компьютеров, которые не имеют ничего общего с разработкой вашего приложения - например, готового к использованию Windows IIS или чего-то еще. Или вы можете использовать Vagrant для предоставления компьютеров для проектов, которые не используют Docker - возможно, они используют комбинацию rubygems и rvm, например, для управления зависимостями и песочницей.
В итоге: Vagrant предназначен для управления машинами, а Docker - для создания и запуска сред приложений.
6 ответов
Это можно сделать со сложностью памяти O (Sqrt (N)) и сложностью процессора O (N * Log (Log (N))) с оптимизированным оконным решетом Эратосфена, как реализовано в пример кода ниже.
Поскольку язык не был указан и я не знаю Python, я реализовал его в VB.net, однако я могу преобразовать его в C #, если вам это нужно.
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
Обратите внимание, что в O ( N * Log (Log (N))), эта процедура факторизует каждое число в среднем на O (Log (Log (N))), что намного, намного быстрее, чем самые быстрые алгоритмы факторизации одиночного N, указанные в некоторых ответах здесь . Фактически, при N = 10 ^ 12 это в 2400 раз быстрее!
Я протестировал эту процедуру на своем ноутбуке Intel Core 2 с частотой 2 ГГц, и она вычисляет более 3 000 000 значений Phi () в секунду. При такой скорости вам потребуется около 4 дней, чтобы вычислить 10 ^ 12 значений. Так же проверил на корректность до 100000000 без ошибок. Он основан на 64-битных целых числах, поэтому все до 2 ^ 63 (10 ^ 19) должно быть точным (хотя и слишком медленным для всех).
У меня также есть Visual Studio WinForm (также VB.net) для запуска / testing, что я могу предоставить, если вы этого хотите.
Дайте мне знать, если у вас есть какие-либо вопросы.
В соответствии с просьбой в комментариях, я добавил ниже версию кода C #. Однако, поскольку я сейчас занимаюсь некоторыми другими проектами, у меня нет времени на его преобразование, поэтому я использовал один из онлайн-сайтов по преобразованию VB в C # ( http://www.carlosag.net / tools / codetranslator / ). Так что имейте в виду, что это было автоматически преобразовано, и у меня еще не было времени проверить или проверить это самостоятельно.
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))));
}
}
Никто не нашел более быстрого способа вычисления phi (k) (также известного как функция Эйлера ), чем сначала нахождение простых множителей k. Лучшие математики мира затратили много циклов процессора на эту проблему с 1977 года, так как поиск более быстрого способа решения этой проблемы привел бы к уязвимости в алгоритме открытого ключа RSA . (И открытый, и закрытый ключ в RSA вычисляются на основе phi (n), где n - произведение двух больших простых чисел.)
The computation of phi(k) has to be done using the prime factorization of k, which is the only sensible way of doing it. If you need a refresher on that, wikipedia carries the formula.
If you now have to compute all prime divisors of every number between 1 and a large N, you'll die of old age before seeing any result, so I'd go the other way around, i.e. build all numbers below N, using their possible prime factors, i.e. all primes less than or equal to N.
Your problem is therefore going to be similar to computing all divisors of a number, only you do not know what is the maximum number of times you may find a certain prime in the factorization beforehand. Tweaking an iterator originally written by Tim Peters on the python list (something I've blogged about...) to include the totient function, a possible implementation in python that yields k, phi(k) pairs could be as follows:
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
If you need help on computing all prime factors below N, I've also blogged about it... Keep in mind, though that computing all primes below 1012 is in itself quite a remarkable feat...
Это из проекта Euler 245? Я помню этот вопрос и отказался от него.
Самый быстрый способ, который я нашел для вычисления totient, состоял в том, чтобы умножить простые множители (p-1) вместе, учитывая, что k не имеет повторяющихся множителей (чего никогда не было. если правильно помню проблему).
Поэтому для вычисления коэффициентов, вероятно, лучше всего использовать gmpy.next_prime или pyecm (факторизация эллиптической кривой).
Вы также можете просеять простые множители, как предлагает Хайме. Для чисел до 10 12 максимальный простой коэффициент меньше 1 миллиона, что должно быть разумным.
Если вы запомните факторизации, это может еще больше ускорить выполнение функции phi.
Для подобных задач я использую итератор, который для каждого целого числа m
С помощью списка простых чисел
Этот метод имеет сложность O ( N log (log ( N ))) в предположении, что все операции, включая операции со списком, принимают O (1).
Думаю, можно пойти другим путем. Вместо того чтобы разложить на множители целое число k для получения phi (k), вы можете попытаться сгенерировать все целые числа от 1 до N из простых чисел и быстро получить phi (k). Например, если P n - максимальное простое число, которое меньше N, вы можете сгенерировать все целые числа меньше N на
P 1 i 1 * P 2 i 2 * ... * P n i n , где каждый i j запускается с От 0 до [log (N) / log (P j )] ([] - минимальная функция).
Таким образом, вы можете быстро получить phi (k) без дорогостоящей простой факторизации и при этом повторять через все k от 1 до N (не по порядку, но я думаю, что вас не волнует порядок).