Генерация уникальных, заказанных Пифагорейских триплетов

Версия 5 Joel Neely.

С тех пор X может быть макс. из 'N-2', и Y может быть макс. из 'N-1' для диапазона 1.. N. С тех пор Z макс. N, и Y макс. является N-1, X может быть макс. из Sqrt (N * N - (N-1) * (N-1)) = Sqrt (2 * N - 1) и может запуститься от 3.

MaxX = ( 2 * N - 1 ) ** 0.5

for x in 3..MaxX {
  y = x+1
  z = y+1
  m = x*x + y*y
  k = z * z
  while z <= N {
     while k < m {
        z = z + 1
        k = k + (2*z) - 1
    }
    if k == m and z <= N then {
        // use x, y, z
    }
    y = y + 1
    m = m + (2 * y) - 1
  }
 }

Да, существует.

Хорошо, теперь Вы захотите знать почему. Почему не просто ограничивают его так, чтобы z> y? Попробуйте

for z in range (y+1, 1000)

Я записал что программа в Ruby и этом подобный реализации Python. Важная строка:

if x*x == y*y + z*z && gcd(y,z) == 1:

Затем необходимо реализовать метод, которые возвращают наибольший общий делитель (GCD) двух данных чисел. Очень простой пример в Ruby снова:

def gcd(a, b)
    while b != 0
      t = b
      b = a%b
      a = t
    end
    return a
end

полный Ruby methon для нахождения триплетов был бы:

def find_triple(upper_boundary)

  (5..upper_boundary).each {|c|
    (4..c-1).each {|b|
      (3..b-1).each {|a|
        if (a*a + b*b == c*c && gcd(a,b) == 1)
          puts "#{a} \t #{b} \t #{c}"
        end
      }
    }
  }
end

def pyth_triplets(n=1000):
    "Version 1"
    for x in xrange(1, n):
        x2= x*x # time saver
        for y in xrange(x+1, n): # y > x
            z2= x2 + y*y
            zs= int(z2**.5)
            if zs*zs == z2:
                yield x, y, zs

>>> print list(pyth_triplets(20))
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]

алгоритм V.1 имеет монотонно увеличение x значения.

РЕДАКТИРОВАНИЕ

кажется, что этот вопрос все еще жив :)
, Так как я возвратился и пересмотрел код, я попробовал второй подход, который почти в 4 раза более быстр (приблизительно 26% процессорного времени для N=10000), чем мое предыдущее предложение, так как это избегает большого количества ненужных вычислений:

def pyth_triplets(n=1000):
    "Version 2"
    for z in xrange(5, n+1):
        z2= z*z # time saver
        x= x2= 1
        y= z - 1; y2= y*y
        while x < y:
            x2_y2= x2 + y2
            if x2_y2 == z2:
                yield x, y, z
                x+= 1; x2= x*x
                y-= 1; y2= y*y
            elif x2_y2 < z2:
                x+= 1; x2= x*x
            else:
                y-= 1; y2= y*y

>>> print list(pyth_triplets(20))
[(3, 4, 5), (6, 8, 10), (5, 12, 13), (9, 12, 15), (8, 15, 17), (12, 16, 20)]

Примечание, что этот алгоритм имеет увеличение z значения.

, Если алгоритм был преобразован в C —, где, будучи ближе к металлу, умножение занимает больше времени, чем additions—, каждый мог minimalise необходимое умножение, учитывая тот факт, что шаг между последовательными квадратами:

(x+1) ВІ - xВІ = (x+1) (x+1) - xВІ = xВІ + 2x + 1 - xВІ = 2x + 1

, таким образом, все внутренние x2= x*x и y2= y*y были бы преобразованы в дополнения и вычитания как это:

def pyth_triplets(n=1000):
    "Version 3"
    for z in xrange(5, n+1):
        z2= z*z # time saver
        x= x2= 1; xstep= 3
        y= z - 1; y2= y*y; ystep= 2*y - 1
        while x < y:
            x2_y2= x2 + y2
            if x2_y2 == z2:
                yield x, y, z
                x+= 1; x2+= xstep; xstep+= 2
                y-= 1; y2-= ystep; ystep-= 2
            elif x2_y2 < z2:
                x+= 1; x2+= xstep; xstep+= 2
            else:
                y-= 1; y2-= ystep; ystep-= 2

, Конечно, в Python дополнительный байт-код, произведенный на самом деле , замедляется алгоритм по сравнению с версией 2, но я держал бы пари (без проверки :) это, V.3 быстрее в C.

Аплодисменты все :)

Алгоритмы могут быть настроены для скорости, использования памяти, простоты и других вещей.

Вот pythagore_triplets алгоритм, настроенный для скорости, за счет использования памяти и простоты. Если все, что Вы хотите, является скоростью, это могло бы быть способом пойти.

Вычисление list(pythagore_triplets(10000)) занимает 40 секунд на моем компьютере, по сравнению с 63 секундами для алгоритма О¤О–О©О¤О–О™ОџОҐ's, и возможно дни вычисления для алгоритма Tafkas (и все другие алгоритмы, которые используют 3 вложенных цикла вместо всего 2).

def pythagore_triplets(n=1000):
   maxn=int(n*(2**0.5))+1 # max int whose square may be the sum of two squares
   squares=[x*x for x in xrange(maxn+1)] # calculate all the squares once
   reverse_squares=dict([(squares[i],i) for i in xrange(maxn+1)]) # x*x=>x
   for x in xrange(1,n):
     x2 = squares[x]
     for y in xrange(x,n+1):
       y2 = squares[y]
       z = reverse_squares.get(x2+y2)
       if z != None:
         yield x,y,z

>>> print list(pythagore_triplets(20))
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]

Примечание, что, если Вы собираетесь вычислить первый миллиард триплетов, затем этот алгоритм откажет, прежде чем это даже запустится, из-за из ошибки памяти. Таким образом, алгоритм О¤О–О©О¤О–О™ОџОҐ's является, вероятно, более безопасным выбором для высоких значений n.

BTW, вот алгоритм Tafkas, переведенный в Python в целях моих тестов производительности. Его дефект состоит в том, чтобы потребовать 3 циклов вместо 2.

def gcd(a, b):
  while b != 0:
    t = b
    b = a%b
    a = t
  return a

def find_triple(upper_boundary=1000):
  for c in xrange(5,upper_boundary+1):
    for b in xrange(4,c):
      for a in xrange(3,b):
        if (a*a + b*b == c*c and gcd(a,b) == 1):
          yield a,b,c

Ранее перечисленные алгоритмы для генерации Пифагорейские триплеты являются всеми модификациями наивного подхода, полученного из основных отношений a^2 + b^2 = c^2, где (a, b, c) триплет положительных целых чисел. Оказывается, что Пифагорейские триплеты удовлетворяют некоторые довольно замечательные отношения, которые могут использоваться для генерации всех Пифагорейских триплетов.

Euclid обнаружил первое такие отношения. Он решил, что для каждого Пифагорейца трижды (a, b, c), возможно после переупорядочения a и b существуют относительно главные положительные целые числа m и n с m > n, по крайней мере один из которых даже, и положительное целое число k таким образом, что

a = k (2mn)
b = k (m^2 - n^2)
c = k (m^2 + n^2)

Затем для генерации Пифагорейских триплетов генерируйте относительно главные положительные целые числа m и n из отличающейся четности и положительное целое число k и примените вышеупомянутую формулу.

struct PythagoreanTriple {
    public int a { get; private set; }
    public int b { get; private set; }
    public int c { get; private set; }

    public PythagoreanTriple(int a, int b, int c) : this() {
        this.a = a < b ? a : b;
        this.b = b < a ? a : b;
        this.c = c;
    }

    public override string ToString() {
        return String.Format("a = {0}, b = {1}, c = {2}", a, b, c);
    }

    public static IEnumerable<PythagoreanTriple> GenerateTriples(int max) {
        var triples = new List<PythagoreanTriple>();
        for (int m = 1; m <= max / 2; m++) {
            for (int n = 1 + (m % 2); n < m; n += 2) {
                if (m.IsRelativelyPrimeTo(n)) {
                    for (int k = 1; k <= max / (m * m + n * n); k++) {
                        triples.Add(EuclidTriple(m, n, k));
                    }
                }
            }
        }

        return triples;
    }

    private static PythagoreanTriple EuclidTriple(int m, int n, int k) {
        int msquared = m * m;
        int nsquared = n * n;
        return new PythagoreanTriple(k * 2 * m * n, k * (msquared - nsquared), k * (msquared + nsquared));
    }
}

public static class IntegerExtensions {
    private static int GreatestCommonDivisor(int m, int n) {
        return (n == 0 ? m : GreatestCommonDivisor(n, m % n));
    }

    public static bool IsRelativelyPrimeTo(this int m, int n) {
        return GreatestCommonDivisor(m, n) == 1;
    }
}

class Program {
    static void Main(string[] args) {
        PythagoreanTriple.GenerateTriples(1000).ToList().ForEach(t => Console.WriteLine(t));            
    }
}

статья Wikipedia о [1 116] Формулы для генерации Пифагорейца утраиваются , содержит другие такие формулы.

Необходимо определить x < y < z.

for x in range (1, 1000):
    for y in range (x + 1, 1000):
            for z in range(y + 1, 1000):

Другая хорошая оптимизация должна была бы только использовать X и Y и вычислить zsqr = x * x + y * y. Если zsqr является квадратным числом (или z = sqrt (zsqr) является целым числом), это - триплет, еще нет. Тем путем Вам нужны только два цикла вместо три (для Вашего примера, это приблизительно в 1000 раз быстрее).

for a in range(1,20):
    for b in range(1,20):
        for c in range(1,20):
            if a>b and c and c>b:
                if a**2==b**2+c**2:
                    print("triplets are:",a,b,c)

Просто проверяю, но я использовал следующий код для создания пифагоровых троек. Это очень быстро (и я пробовал некоторые из примеров здесь, хотя я вроде как выучил их и написал свои собственные, вернулся и проверил здесь (2 года назад)). Я думаю, что этот код правильно находит все пифагоровы тройки вплоть до (назовите свой предел) и тоже довольно быстро. Я использовал C++ для его создания.

ullong - это unsigned long long, и я создал пару функций для возведения в квадрат и корня. Моя функция корня в основном говорила, что если квадратный корень из данного числа (после возведения в квадрат целого числа (интеграл)) не равен числу give, то возвращается -1, потому что это число не корневое. _square и _root делают то, что ожидалось по описанию выше, я знаю другой способ оптимизировать это, но я еще не делал и не тестировал это.

generate(vector<Triple>& triplist, ullong limit) {
cout<<"Please wait as triples are being generated."<<endl;
register ullong a, b, c;
register Triple trip;
time_t timer = time(0);

for(a = 1; a <= limit; ++a) {
    for(b = a + 1; b <= limit; ++b) {
        c = _root(_square(a) + _square(b));

        if(c != -1 && c <= limit) {
            trip.a = a; trip.b = b; trip.c = c;

            triplist.push_back(trip);

        } else if(c > limit)
            break;
    }
}

timer = time(0) - timer;
cout<<"Generated "<<triplist.size()<<" in "<<timer<<" seconds."<<endl;
cin.get();
cin.get();

}

Дайте мне знать, что вы все думаете. Он генерирует все примитивные и непримитивные тройки в соответствии с требованиями преподавателя, которому я его сдавал. (она тестировала его до 100, если я правильно помню).

Результаты от v4, предоставленные предыдущим кодером здесь

Ниже приведен не очень научный набор таймингов (используя Java под Eclipse на моем старом ноутбуке с другими запущенными программами...), где "использовать x, y, z" было реализовано путем инстанцирования объекта Triple с тремя значениями и помещением его в ArrayList. (Для этих запусков N было установлено на 10 000, что дало 12 471 тройку в каждом случае.)

Версия 4: 46 сек. с использованием квадратного корня: 134 сек. массив и карта: 400 сек.

Мои результаты таковы Сколько тройников нужно сгенерировать: 10000

Пожалуйста, подождите, пока генерируются тройки. Сгенерировано 12471 за 2 секунды.

Это еще до того, как я начал оптимизацию через компилятор. (Я помню, что ранее мне удалось свести 10000 к 0 секундам с помощью кучи специальных опций и прочего). Мой код также генерирует все тройки со 100 000 в качестве предела того, насколько высоко могут подняться side1,2,hyp, за 3,2 минуты (я думаю, что для достижения предела в 1 000 000 потребуется час).

Я немного изменил код и снизил предел в 10 000 до 1 секунды (без оптимизаций). Кроме того, при тщательном обдумывании, мой код можно разбить на части и выполнить потоковую обработку в заданных диапазонах (например, 100 000 разделить на 4 равные части для 3 процессоров (1 дополнительный, чтобы надеяться на потребление времени процессора на всякий случай) с диапазонами от 1 до 25 000 (начать с 1 и ограничить до 25 000), от 25 000 до 50 000, от 50 000 до 75 000 и от 75 000 до конца. Я могу сделать это и посмотреть, ускорит ли это процесс (у меня будут предварительно созданные потоки, и я не буду включать их в фактическое количество времени для выполнения тройной функции. Мне нужен более точный таймер и способ конкатенации векторов. Я думаю, что если 1 процессор 3.4 GHZ с 8 gb ram в распоряжении может сделать 10,000 as lim за 1 секунду, то 3 процессора должны сделать это за 1/3 секунды (и я округляю до большей секунды, как есть на данный момент).