GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.3 (4)<< < Пред. | След. > >>   Поиск:  
 Автор Тема: На: Вопрос на засыпку (математика)
гость
91.144.161.*
На: Вопрос на засыпку (математика)
Добавлено: 12 июн 09 13:14
Цитата:
Шире смотрите на теорию чисел.

Я шире и смотрю.
Если взять ряд чисел и отметить 1 простые 0 составные то полученный ряд бит будет иррациональным числом. Вы хотите вычислять иррациональное число без рекурсии и выделения новой памяти?
[Ответ][Цитата]
Dark Welder
Сообщений: 1155
На: Вопрос на засыпку (математика)
Добавлено: 12 июн 09 14:13
Цитата:
Автор: Что-то разумное, типа чувака
В задаче, для числа 65536, множество решений уравнения, следующее:

Строю рисунок для числа 65536 без использования каких-либо ноу-хау и секретных разработок:
http://img180.imagevenue.com/img.php?image=99384_19_122_929lo.jpg
Похоже?
Я не знаю, какую секретную теоретическую базу Вы подводите под свое секретное уравнение, на основании которого строится данный рисунок, но на самом деле его смысл прост:
65536=2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2
Если мы разлагаем число 65536 на два множителя, то:
65536=65536*1=32768*2=16384*4=8192*8=4096*16=2048*32=1024*64=512*128=256*256=128*512=64*1024=32*2048=16*4096=8*8192=4*16384=2*32768=1*65536. Но большинство из этих множителей также можно разложить на множители 2^n. Вот ЭТО Вы где-то зачем-то делаете (возможно неявно) и визуализируете.
То есть если некое число разлагается на более чем два простых множителя, например 1864639=7*41*73*89, то при решении уравнения x*y=1864639 один или оба целочисленных множителя будут также разлагаться на множители. Вот из-за этого и получаются такие красивые рисунки.
Явно или не явно, вы решаете уравнение x*y=z, после чего решаете уравнения a*b=x и a*b=y (все или не все, явно или неявно).
a и b вы визуализируете. А так как z=x*y=y*x, x=a*b=b*a и y=a*b=b*a, то на рисунке получается много точек, симметричных относительно различных осей симметрии.

P.S.
Когда я говорю про недостатки визуализации, я имею ввиду, что приведенный рисунок не до конца отражает суть процесса. Вот что Вы на самом деле визуализируете:
http://img102.imagevenue.com/img.php?image=02959_20_122_367lo.jpg
Условная "дуга", в которую "упираются" точки - решение уравнения x*y=z.
Именно из-за этой дуги, когда Вы на нее "наезжаете" рамкой рисунка (потому что видимую область выбираете произвольно, без учета характера "большого" изображения), на Ваших рисунках может получаться темный правый нижний угол с точками или без.
[Ответ][Цитата]
Что-то разумное, типа чувака
Сообщений: 297
На: Вопрос на засыпку (математика)
Добавлено: 13 июн 09 8:08
Цитата:
Автор: гость

Я шире и смотрю.
Если взять ряд чисел и отметить 1 простые 0 составные то полученный ряд бит будет иррациональным числом. Вы хотите вычислять иррациональное число без рекурсии и выделения новой памяти?


Если бы рекурсией можно было бы охарактеризовать простые числа, то был бы рай на земле.
Кстати, вычисление простых чисел по сравнению с разложением числа на множители это куйня.
На основе аппарата Variable Logic сбацал алгоритм, который натягивает "Решето Эратосфена" по производительности так как сложность этого алгоритма порядка O(ln sqrt N), по сравнению с решетом, где порядка O(ln N) и главное по используемой памяти, порядка O(ln N), а в "РЭ" кошмар сколько памяти надо: порядка O(N).

Итоговое время вычисление всех 78 498 простых чисел размером до 1 000 000, составило 2 секунды.

Если изначально задавать те простые числа, которые знаем, например 2,3,5,7 и т.д. уже непосредственно в структуру алгоритма, что делают при оптимизации алгоритмов "РЭ", приход скорости вычисления это конечно же даст, но не уменьшит сложность алгоритма вобщем. Но можно, но это уже нецелесообразный фанатизм оптимизации алгоритмов.
Алгоритм распараллеливается трудно, но я не говорю, что нет.
Утилитка тут: http://gl-ar.ru/res/prime1.exe

Цитата:
Автор: Dark Welder

Строю рисунок для числа 65536 без использования каких-либо ноу-хау и секретных разработок:
http://img180.imagevenue.com/img.php?image=99384_19_122_929lo.jpg
Похоже?
Я не знаю, какую секретную теоретическую базу Вы подводите под свое секретное уравнение, на основании которого строится данный рисунок, но на самом деле его смысл прост:
65536=2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2
Если мы разлагаем число 65536 на два множителя, то:
65536=65536*1=32768*2=16384*4=8192*8=4096*16=2048*32=1024*64=512*128=256*256=128*512=64*1024=32*2048=16*4096=8*8192=4*16384=2*32768=1*65536. Но большинство из этих множителей также можно разложить на множители 2^n. Вот ЭТО Вы где-то зачем-то делаете (возможно неявно) и визуализируете.
То есть если некое число разлагается на более чем два простых множителя, например 1864639=7*41*73*89, то при решении уравнения x*y=1864639 один или оба целочисленных множителя будут также разлагаться на множители. Вот из-за этого и получаются такие красивые рисунки.
Явно или не явно, вы решаете уравнение x*y=z, после чего решаете уравнения a*b=x и a*b=y (все или не все, явно или неявно).
a и b вы визуализируете. А так как z=x*y=y*x, x=a*b=b*a и y=a*b=b*a, то на рисунке получается много точек, симметричных относительно различных осей симметрии.

P.S.
Когда я говорю про недостатки визуализации, я имею ввиду, что приведенный рисунок не до конца отражает суть процесса. Вот что Вы на самом деле визуализируете:
http://img102.imagevenue.com/img.php?image=02959_20_122_367lo.jpg
Условная "дуга", в которую "упираются" точки - решение уравнения x*y=z.
Именно из-за этой дуги, когда Вы на нее "наезжаете" рамкой рисунка (потому что видимую область выбираете произвольно, без учета характера "большого" изображения), на Ваших рисунках может получаться темный правый нижний угол с точками или без.


Да, уравнение x*y=z, оно самое, просто выглядит...
Но вы используете функциональный анализ и округление, но тут тема сидит глубже в числовом анализе, по крайней мере извращенно-математическую функцию по характеристике численной системы, не видел, что бы кто нибудь строил.
Вот те 5 картинок, где была взята разница на единицу, вы уже округлением не получите.

И еще, плиз, делайте результаты решения в картинке формата БМП, монохроматический, что бы лишней памяти не кушать. ДЖПЭГ искажает изображение т.к. там сжатие с потерей данных. Что бы этой погрешности, так сказать, визуализации не было.

Темное пятно на рисунке: это окружность или гипербола?
С виду вроде окружность, а решением ведь должна быть гипербола (если подходить с точки зрения функционального анализа).
[Ответ][Цитата]
Dark Welder
Сообщений: 1155
На: Вопрос на засыпку (математика)
Добавлено: 13 июн 09 10:24
Цитата:
Автор: Что-то разумное, типа чувака
Итоговое время вычисление всех 78 498 простых чисел размером до 1 000 000, составило 2 секунды.

А что у Вас за компьютер? Результат как-то не очень впечатляет.
На старом E2160@1.86 GHz c 1 GB ОЗУ
78498 простых числа до 1000000 у меня вычисляется за 0.05 сек.
2433654 простых числа до 40000000 у меня вычисляется за 1.96 сек.
[Ответ][Цитата]
Что-то разумное, типа чувака
Сообщений: 297
На: Вопрос на засыпку (математика)
Добавлено: 13 июн 09 10:48
Цитата:
Автор: Dark Welder


А что у Вас за компьютер? Результат как-то не очень впечатляет.
На старом E2160@1.86 GHz c 1 GB ОЗУ
78498 простых числа до 1000000 у меня вычисляется за 0.05 сек.
2433654 простых числа до 40000000 у меня вычисляется за 1.96 сек.


Ну со временем, в 0,05 сек вы загнули....вычисление простых чисел до лимона решетом Аткина заняло где-то 0,3-0,5 сек.
Но в моем алгоритме вычисления простых нет вообще оптимизации.
Если скажем нужно вычислить простые числа до числа лимон в квадрате, то уже можно ручками добавить оптимизацию на всех простых меньше лимона. Прога будет размера в сотню страниц, но зато оптимально
Но, что бы без фанатизма программинга, не писать сотни страниц, можно написать прогу, которая бы писала оптимизацию для изначальной проги.
[Ответ][Цитата]
Dark Welder
Сообщений: 1155
На: Вопрос на засыпку (математика)
Добавлено: 13 июн 09 11:02
Цитата:
Автор: Что-то разумное, типа чувака
Ну со временем, в 0,05 сек вы загнули....вычисление простых чисел до лимона решетом Аткина заняло где-то 0,3-0,5 сек.

Нет, все точно, посмотрел еще раз. Рассчет чисел до 1 млн. занимает 0.048-0.056, а рассчет числе до 40 млн. меньше 2 сек.
[Ответ][Цитата]
Что-то разумное, типа чувака
Сообщений: 297
На: Вопрос на засыпку (математика)
Добавлено: 13 июн 09 11:04
ну, скинь алгоритм плиз....потестим
[Ответ][Цитата]
Dark Welder
Сообщений: 1155
На: Вопрос на засыпку (математика)
Добавлено: 13 июн 09 11:31
Цитата:
Автор: Что-то разумное, типа чувака
ну, скинь алгоритм плиз....потестим


n=1000000;%это число, до которого мы ищем простые числа
p = 1:2:n;
q = length(p);
p(1) = 2;
for k = 3:2:sqrt(n)
if p((k+1)/2)
p(((k*k+1)/2):k:q) = 0;
end
end
p = p(p>0);
[Ответ][Цитата]
Что-то разумное, типа чувака
Сообщений: 297
На: Вопрос на засыпку (математика)
Добавлено: 13 июн 09 11:45
Цитата:
Автор: Dark Welder



n=1000000;%это число, до которого мы ищем простые числа
p = 1:2:n;%выделяем память под массив
q = length(p);
p(1) = 2;
for k = 3:2:sqrt(n)
if p((k+1)/2)
p(((k*k+1)/2):k:q) = 0;
end
end
p = p(p>0);


Что значит length(p)?
И вот эту строчку прокомментируй: p(((k*k+1)/2):k:q) = 0;
[Ответ][Цитата]
Dark Welder
Сообщений: 1155
На: Вопрос на засыпку (математика)
Добавлено: 13 июн 09 12:22
Цитата:
Автор: Что-то разумное, типа чувака
Что значит length(p)?

длина вектора p, состоящего из нечетных чисел.
Цитата:
Автор: Что-то разумное, типа чувака
И вот эту строчку прокомментируй: p(((k*k+1)/2):k:q) = 0;

Это цикл, который обнуляет все элементы вектора p, начиная с элемента (k*k+1)/2 с шагом k до конца вектора p.

В этом алгоритме в векторе p, состоящем из нечетных чисел, обнуляются те числа, который являются кратными другим числам, входящим в этот вектор. В результате в векторе остаются только простые числа и нули. Нули последней строчкой исключаются, в векторе остаются только простые числа.
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Вопрос на засыпку (математика)
Добавлено: 13 июн 09 13:52
Да, разложение на простые задача важнее чем генерация. Генерация и нужна-то в основном чтобы знать на что разлогать.

Скорость должна быть как у Dark Welder. Я считал до 100млн
http://www.aicommunity.org/members/no/img/no-simple.gif
Там по последним двум битам простых чисел выбираем направление движения и вот такое нарисовалось.
[Ответ][Цитата]
Dark Welder
Сообщений: 1155
На: Вопрос на засыпку (математика)
Добавлено: 13 июн 09 20:18
Цитата:
Автор: Что-то разумное, типа чувака
Но вы используете функциональный анализ и округление, но тут тема сидит глубже в числовом анализе, по крайней мере извращенно-математическую функцию по характеристике численной системы, не видел, что бы кто нибудь строил.
Вот те 5 картинок, где была взята разница на единицу, вы уже округлением не получите.

Нет, никакого округления я не использую.
А по поводу Ваших картинок - назовите числа, которым они соотвествуют, посмотрим, что у меня получится.
Цитата:
Автор: Что-то разумное, типа чувака
И еще, плиз, делайте результаты решения в картинке формата БМП, монохроматический, что бы лишней памяти не кушать. ДЖПЭГ искажает изображение т.к. там сжатие с потерей данных. Что бы этой погрешности, так сказать, визуализации не было.

Пока технически это не возможно.
Цитата:
Автор: Что-то разумное, типа чувака
Темное пятно на рисунке: это окружность или гипербола?
С виду вроде окружность, а решением ведь должна быть гипербола (если подходить с точки зрения функционального анализа).

Вот в другом масштабе.
http://img258.imagevenue.com/img.php?image=09657_21_122_75lo.jpg

Кстати, посмотрел еще раз время - на нормальном компьютере рассчет чисел до 1 млн. занял 0.021 сек.
[Ответ][Цитата]
Что-то разумное, типа чувака
Сообщений: 297
На: Вопрос на засыпку (математика)
Добавлено: 14 июн 09 7:52
Цитата:
Автор: Dark Welder

n=1000000;%это число, до которого мы ищем простые числа
p = 1:2:n;
q = length(p);
p(1) = 2;
for k = 3:2:sqrt(n)
if p((k+1)/2)
p(((k*k+1)/2):k:q) = 0;
end
end
p = p(p>0);


Алгоритм ясен, это и есть решето Эратосфена оптимизированное один раз по простому числу 2.
Алгоритм частенько вычеркивает одно и тоже число несколько раз и оптимизация алгоритма состоит в том, что бы уменьшить количество повторных вычеркиваний в процессе работы.
Оптимизация на 2 позволяет пропустить 500 000 шагов вычеркивания 2-ки и четные числа не будут вычеркиваться более 2-х раз. Так как чисел делящихся на 2 в натуральном больше чем чисел делящихся на другое простое число, то оптимизация на 2 является самой продуктивной.
Возможно ли сделать 2-й шаг оптимизации на 3? Возможно, но только не в этой форме. Оптимизация по принципу игнорирования обработки четных чисел и путем использования процедур /2, ставит в тупик дальнейший подход в оптимизации. Но если свести алгоритм к изначальному не оптимизированному виду, и задав в общем виде критерии оптимизации, вариацией которых можно строить функцию, увеличение размера которой будет уменьшать время вычисления алгоритма. В идеале, составить алгоритм, который сам будет строить эту функцию оптимизации, в итоге во время работы алгоритм ни разу не вычеркнет число 2 раза, так сказать самооптимизирующийся алгоритм.
Попробуйте.

Цитата:
Автор: Dark Welder

Нет, никакого округления я не использую.
А по поводу Ваших картинок - назовите числа, которым они соотвествуют, посмотрим, что у меня получится.



257


260


263


264


267


272


284

Число соответствует размеру стороны квадрата.
Картинки симметричны по обоим диагоналям, кроме последней.

Цитата:
Автор: Dark Welder

Пока технически это не возможно.


На экране вы же получали эту картинку? => принт скрин => паинт => паст => сайф ас бмп...
[Ответ][Цитата]
Что-то разумное, типа чувака
Сообщений: 297
На: Вопрос на засыпку (математика)
Добавлено: 14 июн 09 7:55
Цитата:
Автор: NO.

http://www.aicommunity.org/members/no/img/no-simple.gif
Там по последним двум битам простых чисел выбираем направление движения и вот такое нарисовалось.


Красивая картинка, но математического смысла она не имеет.
И еще, непонятно, ведь для любого простого числа, кроме числа 10, последний бит равен 1. Может быть вы хотели сказать по двум предпоследним битам?
[Ответ][Цитата]
Что-то разумное, типа чувака
Сообщений: 297
На: Вопрос на засыпку (математика)
Добавлено: 14 июн 09 8:40
to Dark Welder:

Обнаружено число, с которого начинается асимметрия для этого уравнения: 273, не простое = 3*7*13.
И числовая асимметрия постепенно нарастает:


317


339
[Ответ][Цитата]
 Стр.3 (4)1  2  [3]  4<< < Пред. | След. > >>