Четыре оттенка нуля или 5-ти битное кодирование в ЭКА

[Soul Friend]

wrest в сообщении #1426017 писал(а):

Вы зря на Dmitriy40 нападаете,

отнюдь, я отбиваюсь ) . Извращение, непонятная нумерология, кривая запись, идиотская - это не мои слова, на минуточку.
Ну он разобрался, по сути ничего сложного.

wrest в сообщении #1426017 писал(а):

А кстати: сколько вы хотите вычислить значений центральной колонны, и как будете определять есть ли периодичность там?

В первом посте я писал, что уже в тупике, и делюсь с другими этим методом декомпозиций. Может кому повезёт больше.

[Dmitriy40]

Мда, а со скоростью вычислений не так всё плохо как я думал. Если хранить не битовые строки, а именно что многобитные числа, то ускорение будет ровно в $k^2$ раз, где $k$ - по сколько бит в числе хранить. Сейчас сделал на PARI с восьмеричными цифрами (0..7), но без всякого перекрытия разумеется, просто побил исходную битовую строку на непересекающиеся группы по 3 бита и создал таблицу зависимости уже в базисе этих цифр (вычисляется на лету, думать лень), ускорение получилось с 4.7с для битовой строки в 3001 ячеек до 0.53с для 1001 восьмеричной цифры и с 43.7с для 9001 бита до 4.8с для 3001 восьмеричной цифры, честные 9 раз, это время расчёта всех итераций.
А значит никто не мешает сделать на PARI вычисление сразу по 10 бит чисел, с таблицей всего 4096 ячеек (влезают в кэш L2 процессора) и ускорением в миллион раз. А то AVX, асм, размечтался.

-- 14.11.2019, 22:55 --

Сделал, проверил, при увеличении количества бит $k$ в числах время расчёта на PARI всех первых N итераций падает почти линейно по $k$, с 53.4с для $k=1$ до 5.27с для $k=11$ (это для 5К первых итераций и 10К битов). Ускорения в миллион раз не получилось, эх ... разве только в расчёте на число/ячейку.

[Soul Friend]

Dmitriy40 в сообщении #1426014 писал(а):

если её нет в числах $b_2$.

Вы имеете ввиду доказанный факт о том что две соседние клетки непериодичны относительно друг друга?

-- 15.11.2019, 07:32 --

Soul Friend в сообщении #1425880 писал(а):

Может кто поможет найти для этих последовательностей правильное название и код в PARI/GP.

Я имел ввиду, те кто зарегистрирован в OEIS сделает правки там под своим именем.

[Soul Friend]

Soul Friend в сообщении #1426042 писал(а):

Dmitriy40 в сообщении #1426014

писал(а):
если её нет в числах $b_2$.
Вы имеете ввиду доказанный факт о том что две соседние клетки непериодичны относительно друг друга?

Вы имеете ввиду доказанный факт о том что два соседних столбца непериодичны относительно друг друга? (Или там говорится про любые два столбца?)
гуглить: Aperiodicity in one-dimensional cellular automata.
(время правки текста истекло, извиняюсь за дублирование)

[Soul Friend]

Можно последовать примеру Вольфрама и генерировать псевдослучайные числа этим способом.

{M=matrix(100,201);
M[1,101]=1;M[1,100]=1;M[1,97]=1;M[1,103]=1;
for(i=2,100, for(j=2, 200, if(M[i-1,j-1]==1&&M[i-1,j]==1&&M[i-1,j+1]==1, M[i,j]=0);
if(M[i-1,j-1]==1&&M[i-1,j]==1&&M[i-1,j+1]==0, M[i,j]=0);
if(M[i-1,j-1]==1&&M[i-1,j]==0&&M[i-1,j+1]==1, M[i,j]=0);
if(M[i-1,j-1]==1&&M[i-1,j]==0&&M[i-1,j+1]==0, M[i,j]=1);
if(M[i-1,j-1]==0&&M[i-1,j]==1&&M[i-1,j+1]==1, M[i,j]=1);
if(M[i-1,j-1]==0&&M[i-1,j]==1&&M[i-1,j+1]==0, M[i,j]=1);
if(M[i-1,j-1]==0&&M[i-1,j]==0&&M[i-1,j+1]==1, M[i,j]=1);
if(M[i-1,j-1]==0&&M[i-1,j]==0&&M[i-1,j+1]==0, M[i,j]=0) ));

N=matrix(100,201);
N[1,101]=1;
for(i=2,100, for(j=2, 200, if(M[i-1,j-1]==1&&M[i-1,j]==1&&M[i-1,j+1]==1, N[i,j]=7);
if(M[i-1,j-1]==1&&M[i-1,j]==1&&M[i-1,j+1]==0, N[i,j]=6);
if(M[i-1,j-1]==1&&M[i-1,j]==0&&M[i-1,j+1]==1, N[i,j]=5);
if(M[i-1,j-1]==1&&M[i-1,j]==0&&M[i-1,j+1]==0, N[i,j]=4);
if(M[i-1,j-1]==0&&M[i-1,j]==1&&M[i-1,j+1]==1, N[i,j]=3);
if(M[i-1,j-1]==0&&M[i-1,j]==1&&M[i-1,j+1]==0, N[i,j]=2);
if(M[i-1,j-1]==0&&M[i-1,j]==0&&M[i-1,j+1]==1, N[i,j]=1);
if(M[i-1,j-1]==0&&M[i-1,j]==0&&M[i-1,j+1]==0, N[i,j]=0) ));
L=matrix(100,201);
L[1,101]=1;
for(i=2,100, for(j=2, 200, 
if(N[i-1,j-1]==0&&N[i-1,j]==0&&N[i-1,j+1]==0, L[i,j]=0);
if(N[i-1,j-1]==0&&N[i-1,j]==0&&N[i-1,j+1]==1, L[i,j]=1);
if(N[i-1,j-1]==0&&N[i-1,j]==1&&N[i-1,j+1]==2, L[i,j]=2);
if(N[i-1,j-1]==0&&N[i-1,j]==1&&N[i-1,j+1]==3, L[i,j]=3);
if(N[i-1,j-1]==1&&N[i-1,j]==2&&N[i-1,j+1]==4, L[i,j]=4);
if(N[i-1,j-1]==1&&N[i-1,j]==2&&N[i-1,j+1]==5, L[i,j]=5);
if(N[i-1,j-1]==1&&N[i-1,j]==3&&N[i-1,j+1]==6, L[i,j]=6);
if(N[i-1,j-1]==1&&N[i-1,j]==3&&N[i-1,j+1]==7, L[i,j]=7); 
if(N[i-1,j-1]==2&&N[i-1,j]==4&&N[i-1,j+1]==0, L[i,j]=8);
if(N[i-1,j-1]==2&&N[i-1,j]==4&&N[i-1,j+1]==1, L[i,j]=9);
if(N[i-1,j-1]==2&&N[i-1,j]==5&&N[i-1,j+1]==2, L[i,j]=10);
if(N[i-1,j-1]==2&&N[i-1,j]==5&&N[i-1,j+1]==3, L[i,j]=11);
if(N[i-1,j-1]==3&&N[i-1,j]==6&&N[i-1,j+1]==4, L[i,j]=12);
if(N[i-1,j-1]==3&&N[i-1,j]==6&&N[i-1,j+1]==5, L[i,j]=13);
if(N[i-1,j-1]==3&&N[i-1,j]==7&&N[i-1,j+1]==6, L[i,j]=14);
if(N[i-1,j-1]==3&&N[i-1,j]==7&&N[i-1,j+1]==7, L[i,j]=15);
if(N[i-1,j-1]==4&&N[i-1,j]==0&&N[i-1,j+1]==0, L[i,j]=16);
if(N[i-1,j-1]==4&&N[i-1,j]==0&&N[i-1,j+1]==1, L[i,j]=17);
if(N[i-1,j-1]==4&&N[i-1,j]==1&&N[i-1,j+1]==2, L[i,j]=18);
if(N[i-1,j-1]==4&&N[i-1,j]==1&&N[i-1,j+1]==3, L[i,j]=19);
if(N[i-1,j-1]==5&&N[i-1,j]==2&&N[i-1,j+1]==4, L[i,j]=20);
if(N[i-1,j-1]==5&&N[i-1,j]==2&&N[i-1,j+1]==5, L[i,j]=21);
if(N[i-1,j-1]==5&&N[i-1,j]==3&&N[i-1,j+1]==6, L[i,j]=22);
if(N[i-1,j-1]==5&&N[i-1,j]==3&&N[i-1,j+1]==7, L[i,j]=23);
if(N[i-1,j-1]==6&&N[i-1,j]==4&&N[i-1,j+1]==0, L[i,j]=24);
if(N[i-1,j-1]==6&&N[i-1,j]==4&&N[i-1,j+1]==1, L[i,j]=25);
if(N[i-1,j-1]==6&&N[i-1,j]==5&&N[i-1,j+1]==2, L[i,j]=26);
if(N[i-1,j-1]==6&&N[i-1,j]==5&&N[i-1,j+1]==3, L[i,j]=27);
if(N[i-1,j-1]==7&&N[i-1,j]==6&&N[i-1,j+1]==4, L[i,j]=28);
if(N[i-1,j-1]==7&&N[i-1,j]==6&&N[i-1,j+1]==5, L[i,j]=29);
if(N[i-1,j-1]==7&&N[i-1,j]==7&&N[i-1,j+1]==6, L[i,j]=30);
if(N[i-1,j-1]==7&&N[i-1,j]==7&&N[i-1,j+1]==7, L[i,j]=31)));
for(i=1, 100, print1(L[i, 101], ", ") )
}

1, 0, 13, 25, 7, 12, 26, 2, 6, 28, 3, 6, 13, 25, 23, 4, 14, 8, 13,
 25, 7, 28, 18, 30, 0, 1, 3, 22, 5, 13, 9, 15, 24, 5, 13, 9, 31, 16,
 24, 5, 13, 9, 31, 0, 16, 9, 31, 0, 0, 1, 19, 30, 17, 27, 18, 30, 0,
 1, 3, 6, 12, 27, 2, 23, 20, 23, 20, 22, 4, 15, 24, 4, 14, 24, 5, 13,
 9, 15, 24, 20, 7, 12, 26, 2, 6, 12, 11, 10, 11, 10, 11, 26, 19, 14,
 8, 13, 25, 7, 28, 2

только числа от нуля до 31, зато не периодичные.

[wrest]

Soul Friend
Из того что я прочитал в блоге Вольфрама, я так понял что он за 40 лет пробовал и так и сяк и наперекосяк, и все равно последовательность в центральной колонке проявляет себя только как случайная.
В частности, он пробовал и архиваторами архивировать, и статистическими методами выявлять неслучайность (и писал статью в applied mathematics в 1986 году об этом), и нейронные сети натравливал, и какой-то там deep learning, и делал эту колонку генератором случайных чисел в вольфрам математике и никто не жаловался на неслучайность и т.д. и т.п.
Такшта вам с вашим пятибитным кодированием надо не только вычислить центральную колонку достаточно далеко, но и прикинуть как именно вы собираетесь искать закономерности в ней...

[Soul Friend]

wrest в сообщении #1426064 писал(а):

Такшта вам с вашим пятибитным кодированием надо не только вычислить центральную колонку достаточно далеко, но и прикинуть как именно вы собираетесь искать закономерности в ней...

А может я хочу доказать не периодичность? Такшта, это палка с двумя концами.
К слову, я ведь писал в самом первом посте:

Soul Friend в сообщении #1425851 писал(а):

Так и не смог доказать непериодичность этой последовательности, делюсь мыслями, может у кого-то получится продвинуть идею дальше.

[wrest]

Soul Friend в сообщении #1426067 писал(а):

А может я хочу доказать не периодичность? Такшта, это палка с двумя концами.

Ну, в любом случае, смотреть на ваши бесконечные if-ы доставляет моральные страдания.
Например, значение N[i-1,j] вообще не влияет на L[i,j] никак.

С учетом этого, нижний монстр из if-ов сокращается до:
for(i=2,100, for(j=2, 200,L[i,j]=8*(N[i-1,j-1] \ 2) + N[i-1,j+1]))

-- 15.11.2019, 13:05 --

Soul Friend в сообщении #1426067 писал(а):

К слову, я ведь писал в самом первом посте:

А я вам отвечаю на другое:

Soul Friend в сообщении #1425880 писал(а):

Может кто поможет найти для этих последовательностей правильное название и код в PARI/GP.

То что вы с наскоку ничего не найдёте и так ясно, Вольфрам 40 лет по пустыне ходил искал и не нашёл. Озарение (в вашем мозгу) конечно не исключается, мало ли, но я тут пишу чисто по PARI/GP

[Soul Friend]

wrest в сообщении #1426071 писал(а):

Ну, в любом случае, смотреть на ваши бесконечные if-ы доставляет моральные страдания.

Мне тоже, но на большее в PARI я пока не способен. Копипаст выручает.

wrest в сообщении #1426071 писал(а):

С учетом этого, нижний монстр из if-ов сокращается до:
for(i=2,100, for(j=2, 200,L[i,j]=8*(N[i-1,j-1] \ 2) + N[i-1,j+1]))

у меня выдает ошибку

incorrect type in &_[_,_] OCcompo2ptr [not a matrix] (t_POL).

Можете написать полный код, или сказать что нужно объявить и куда вставлять этот кусок кода?

[wrest]

Soul Friend в сообщении #1426077 писал(а):

Можете написать полный код,

Используется синтаксис C

{M=matrix(100,201);
M[1,101]=1;M[1,100]=1;M[1,97]=1;M[1,103]=1;
for(i=2,100, for(j=2, 200, if(M[i-1,j-1]==1&&M[i-1,j]==1&&M[i-1,j+1]==1, M[i,j]=0);
if(M[i-1,j-1]==1&&M[i-1,j]==1&&M[i-1,j+1]==0, M[i,j]=0);
if(M[i-1,j-1]==1&&M[i-1,j]==0&&M[i-1,j+1]==1, M[i,j]=0);
if(M[i-1,j-1]==1&&M[i-1,j]==0&&M[i-1,j+1]==0, M[i,j]=1);
if(M[i-1,j-1]==0&&M[i-1,j]==1&&M[i-1,j+1]==1, M[i,j]=1);
if(M[i-1,j-1]==0&&M[i-1,j]==1&&M[i-1,j+1]==0, M[i,j]=1);
if(M[i-1,j-1]==0&&M[i-1,j]==0&&M[i-1,j+1]==1, M[i,j]=1);
if(M[i-1,j-1]==0&&M[i-1,j]==0&&M[i-1,j+1]==0, M[i,j]=0) ));
 
N=matrix(100,201);
N[1,101]=1;
for(i=2,100, for(j=2, 200, if(M[i-1,j-1]==1&&M[i-1,j]==1&&M[i-1,j+1]==1, N[i,j]=7);
if(M[i-1,j-1]==1&&M[i-1,j]==1&&M[i-1,j+1]==0, N[i,j]=6);
if(M[i-1,j-1]==1&&M[i-1,j]==0&&M[i-1,j+1]==1, N[i,j]=5);
if(M[i-1,j-1]==1&&M[i-1,j]==0&&M[i-1,j+1]==0, N[i,j]=4);
if(M[i-1,j-1]==0&&M[i-1,j]==1&&M[i-1,j+1]==1, N[i,j]=3);
if(M[i-1,j-1]==0&&M[i-1,j]==1&&M[i-1,j+1]==0, N[i,j]=2);
if(M[i-1,j-1]==0&&M[i-1,j]==0&&M[i-1,j+1]==1, N[i,j]=1);
if(M[i-1,j-1]==0&&M[i-1,j]==0&&M[i-1,j+1]==0, N[i,j]=0) ));
L=matrix(100,201);
L[1,101]=1;
for(i=2,100, for(j=2, 200,L[i,j]=8*(N[i-1,j-1] \ 2) + N[i-1,j+1]));
for(i=1, 100, print1(L[i, 101], ", ") )
}

24-я строка.

[Soul Friend]

wrest
чётко,
можно использовать на OEIS?

[wrest]

Soul Friend в сообщении #1426088 писал(а):

можно использовать на OEIS?

Это очень плохой код, я бы на OEIS не выкладывал.

1. Вы используете двумерные массивы там, где не надо, а это память.
2. Вы используете массив фиксированного размера, а значит ваша программа только вычислит 100 чисел и не больше, то есть не является универсальной.
3. Ваша программа печатает числа, а должна, вообще-то, возвращать.
4. Куча if-ов там не нужна, плюс, написано так, что проверяются все условия, даже если значение уже вычислено. А это время (из 8 проверок в обоих циклах в среднем надо делать по 4, так что замедление минимум в 4 раза).
5. Вы так и не объяснили что там вычисляется. В итоге привлекли к вычислению данные, как я написал выше, которые не влияют на результат. Число N[i-1,j] непосредственно "над" обрабатываемой ячейкой L[i,j] в вашем коде, на неё не влияет и отсюда вопрос: то ли вы на самом деле вычисляете, что хотите?

[Dmitriy40]

Я повторю предложение заменить каждую кучу if-ов на выборку из массива. Ну или на прямые вычисления как wrest предложил. Это и ускорит, и понятнее.

wrest в сообщении #1426071 писал(а):

Например, значение N[i-1,j] вообще не влияет на L[i,j] никак.

Мне интересно, а как это поняли? Я из последней кучи if-ов этого не вижу, может надо смотреть вместе с предыдущей кучей?

UPD. Какой кошмар эти кучи if-ов! Вторая куча преобразует двоичную запись в десятичную, что можно сделать банально N[i,j]=M[i-1,j-1]*4+M[i-1,j]*2+M[i-1,j+1]; - вот и вся вторая куча if-ов!
А как первую сделать выборкой из rule[] я уже писал в своих программах выше.
UPD2. И кстати, если в результате нужен лишь центральный столбец матрицы L, то матрицы N и L вообще не нужны, столбец L можно вычислить прямо по 9 центральным элементам матрицы M.

[Soul Friend]

Двумерные массивы использовал чтобы увидеть всю картину полностью, то есть напечатать матрицу и посмотреть как распределяются десятичные числа, матрица расширяемая, но да, с увеличением матрицы увеличивается и время вычисления. Один раз вычислив матрицу можно удобно манипулировать её значениями.
Как иначе создавать элементарные клеточные автоматы на PARI и иметь доступ к любым её значениям я не знаю.

Dmitriy40 в сообщении #1426114 писал(а):

Я повторю предложение заменить каждую кучу if-ов на выборку из массива.

Если бы я понимал о чём вы, яж не программист, а такк. Но я думаю над этим.

-- 15.11.2019, 19:35 --

Dmitriy40 в сообщении #1426114 писал(а):

Какой кошмар эти кучи if-ов! Вторая куча преобразует двоичную запись в десятичную, что можно сделать банально N[i,j]=M[i-1,j-1]*4+M[i-1,j]*2+M[i-1,j+1]; - вот и вся вторая куча if-ов!

Даа, математика в программировании это сила!
Ну напишите, пожалуйста, весь код с выборкой rule[] , чтобы уже поставить на этом всём жирную точку.

[wrest]

Dmitriy40 в сообщении #1426114 писал(а):

Мне интересно, а как это поняли? Я из последней кучи if-ов этого не вижу, может надо смотреть вместе с предыдущей кучей?

Ну вот как раз там и видно. Посмотрите формулу что я сделал: "левую" ячейку сперва сдвигаем на один бит вправо (выкидывая младший бит) затем на три бита влево (это делает конструкция 8*(N[i-1,j-1] \ 2), можно и shift-ом типа shift(shift(N[i-1,j-1],-1),3) но вряд ли быстрее будет а тумана кажись больше) и прибавляем "правую" ячейку N[i-1,j+1]. Ну а "средняя" ячейка N[i-1,j] выходит что и не нужна.

Dmitriy40 в сообщении #1426114 писал(а):

Я из последней кучи if-ов этого не вижу, может надо смотреть вместе с предыдущей кучей?

Не, предыдущие не нужны, всё видно там.