Решил опробовать силы на поприще поиска простых чисел. Поставил перед собой задачу - придумать собственный алгоритм перебора. Что из этого получилось - можете посмотреть во вложении =) Отдельные грани вопроса под спойлерами.
Предыстория вопроса.
На работе коллега увлекается программированием на языке Ruby. И решили мы с ним посоревноваться, кто придумает более быстрый алгоритм перебора простых чисел. В тот раз на VBA я потерпел поражение - всё-таки VBA язык интерпретируемый, да и виртуальная машина у него (суть Excel) далека от идеала.
Недавно начал ходить на курсы Java и уж на поприще компилируемых языков всё получилось. Тестировали на переборе чисел до миллиона, алгоритм друга - в среднем 500-600 мс (не считая вывода на экран) на разных машинах, мой алгоритм - от 60 до 150 мс. И вдруг пришла мысль - а почему бы не перенести общий смысл алгоритма на VBA?
Мимолётный взгляд на тематику.
На нашем форуме не нашёл ничего про перебор простых чисел. Есть несколько интересных решений на дружественном сайте ЗДЕСЬ (Планета Эксель). Также из разговоров со знающими людьми узнал, что есть некое Решето Аткина - самый оптимальный алгоритм по скорости и количеству затрачиваемых ресурсов. И, хотя в моём алгоритме используется совершенно другая модель, обнаружил несколько пересечений - маленьких идей, формирующих часть фундамента программы.
Особенности моего алгоритма.
- Весь просматриваемый массив чисел делится на блоки по 12 чисел. - В каждом блоке просматриваются только 4 числа (1-е, 5-е, 7-е и 11-е), остальные гарантированно НЕ простые. - При поиске делителей проверяемого числа, перебираются уже найденные простые числа до такого, квадрат которого больше проверяемого.
Анекдот в тему.
Прошедший 2014-й год был не простым. Непростыми будут и следующие 2015-й и 2016-й года. А вот 2017 снова будет простым. (с) Незнамо чьё.
Всем привет и хорошего настроения!
Решил опробовать силы на поприще поиска простых чисел. Поставил перед собой задачу - придумать собственный алгоритм перебора. Что из этого получилось - можете посмотреть во вложении =) Отдельные грани вопроса под спойлерами.
Предыстория вопроса.
На работе коллега увлекается программированием на языке Ruby. И решили мы с ним посоревноваться, кто придумает более быстрый алгоритм перебора простых чисел. В тот раз на VBA я потерпел поражение - всё-таки VBA язык интерпретируемый, да и виртуальная машина у него (суть Excel) далека от идеала.
Недавно начал ходить на курсы Java и уж на поприще компилируемых языков всё получилось. Тестировали на переборе чисел до миллиона, алгоритм друга - в среднем 500-600 мс (не считая вывода на экран) на разных машинах, мой алгоритм - от 60 до 150 мс. И вдруг пришла мысль - а почему бы не перенести общий смысл алгоритма на VBA?
Мимолётный взгляд на тематику.
На нашем форуме не нашёл ничего про перебор простых чисел. Есть несколько интересных решений на дружественном сайте ЗДЕСЬ (Планета Эксель). Также из разговоров со знающими людьми узнал, что есть некое Решето Аткина - самый оптимальный алгоритм по скорости и количеству затрачиваемых ресурсов. И, хотя в моём алгоритме используется совершенно другая модель, обнаружил несколько пересечений - маленьких идей, формирующих часть фундамента программы.
Особенности моего алгоритма.
- Весь просматриваемый массив чисел делится на блоки по 12 чисел. - В каждом блоке просматриваются только 4 числа (1-е, 5-е, 7-е и 11-е), остальные гарантированно НЕ простые. - При поиске делителей проверяемого числа, перебираются уже найденные простые числа до такого, квадрат которого больше проверяемого.
Анекдот в тему.
Прошедший 2014-й год был не простым. Непростыми будут и следующие 2015-й и 2016-й года. А вот 2017 снова будет простым. (с) Незнамо чьё.
Поставил перед собой задачу - придумать собственный алгоритм перебора
Роман, данный вопрос уже был рассмотрен Эратосфеном более двух тысяч лет тому назад.
В файле пример подсчета количества простых чисел до определенного. Решено с помощью решета Эратосфена с делением диапазонов чисел на блоки. Алгоритм достаточно быстрый. Вывод чисел не предусмотрен, в виду большого их количества (но реализовать вывод в файл или на лист - не проблема).
Публиковалось на Cyberforum Подсчет количества простых чисел от 1 до 100 млрд. на моем компьютере составил 42 минуты.
Поставил перед собой задачу - придумать собственный алгоритм перебора
Роман, данный вопрос уже был рассмотрен Эратосфеном более двух тысяч лет тому назад.
В файле пример подсчета количества простых чисел до определенного. Решено с помощью решета Эратосфена с делением диапазонов чисел на блоки. Алгоритм достаточно быстрый. Вывод чисел не предусмотрен, в виду большого их количества (но реализовать вывод в файл или на лист - не проблема).
Публиковалось на Cyberforum Подсчет количества простых чисел от 1 до 100 млрд. на моем компьютере составил 42 минуты.MCH
какая разница на чем программировать алгоритм на VB или VBA
Не знаю. В начале моего VBA пути я палкой VB потыкал-потыкал, ужаснулся какой разный у программ синтаксис и с тех пор стараюсь о пугающем VB не думать =) Для меня сейчас есть только один Visual Basic - тот, что для приложений. Всё остальное - ересь и извращение =) Да и что-то тогда материалов толковых не нашёл. По VBA пруд-пруди, а VB как будто совершил убийство и старается за собой заметать следы.
какая разница на чем программировать алгоритм на VB или VBA
Не знаю. В начале моего VBA пути я палкой VB потыкал-потыкал, ужаснулся какой разный у программ синтаксис и с тех пор стараюсь о пугающем VB не думать =) Для меня сейчас есть только один Visual Basic - тот, что для приложений. Всё остальное - ересь и извращение =) Да и что-то тогда материалов толковых не нашёл. По VBA пруд-пруди, а VB как будто совершил убийство и старается за собой заметать следы.Rioran
Роман, Москва, voronov_rv@mail.ru Яндекс-Деньги: 41001312674279
Сообщение отредактировал Rioran - Вторник, 03.02.2015, 01:21
Тестировали на переборе чисел до миллиона, алгоритм друга - в среднем 500-600 мс (не считая вывода на экран) на разных машинах, мой алгоритм - от 60 до 150 мс. И вдруг пришла мысль - а почему бы не перенести общий смысл алгоритма на VBA?
Роман, а моим алгоритмом (т.е. решетом Эратосфена, если быть честным, в моей интерпретации) какова скорость по твоим измерениям?
Тестировали на переборе чисел до миллиона, алгоритм друга - в среднем 500-600 мс (не считая вывода на экран) на разных машинах, мой алгоритм - от 60 до 150 мс. И вдруг пришла мысль - а почему бы не перенести общий смысл алгоритма на VBA?
Роман, а моим алгоритмом (т.е. решетом Эратосфена, если быть честным, в моей интерпретации) какова скорость по твоим измерениям?MCH
MCH, на прошлой неделе поверхностно посмотрел твой код. Сходу как задать ровно миллион для перебора - не нашел. Наверно, слишком активно отдыхал во время отпуска =) Сейчас нет возможности уделить этому внимание. Не мог бы ты настроить код на перебор лимона и добавить счётчик миллисекунд?
MCH, на прошлой неделе поверхностно посмотрел твой код. Сходу как задать ровно миллион для перебора - не нашел. Наверно, слишком активно отдыхал во время отпуска =) Сейчас нет возможности уделить этому внимание. Не мог бы ты настроить код на перебор лимона и добавить счётчик миллисекунд?Rioran
Роман, Москва, voronov_rv@mail.ru Яндекс-Деньги: 41001312674279
Сходу как задать ровно миллион для перебора - не нашел
Самая верхняя строчка в процедуре: константа n. Нужно записать [vba]
Код
Const n As Double = 1000000
[/vba] Расчет милисекунд не делал (и даже не знаю как его прикрутить), но там считается в секундах, у меня подсчет колиества простых чисел в диапазоне от 1 до 1 млн занимает 0,059 - 0,07 сек
Сходу как задать ровно миллион для перебора - не нашел
Самая верхняя строчка в процедуре: константа n. Нужно записать [vba]
Код
Const n As Double = 1000000
[/vba] Расчет милисекунд не делал (и даже не знаю как его прикрутить), но там считается в секундах, у меня подсчет колиества простых чисел в диапазоне от 1 до 1 млн занимает 0,059 - 0,07 секMCH
MCH, спасибо. Я сначала так и подумал, но витиеватость дальнейших вычислений призвала к осторожности.
Полез искать надежный и валидный таймер. На основании ЭТОЙ темы пришёл к выводу, что провести измерение можно с помощью библиотек Windows, опирающихся на тики процессора. Такое измерение ненадёжно, воспроизводимость результатов низкая, переносимость на другие машины не сравнимая.
Позже сравню алгоритмы на больших переборах, сравнивая целые секунды исполнения.
MCH, спасибо. Я сначала так и подумал, но витиеватость дальнейших вычислений призвала к осторожности.
Полез искать надежный и валидный таймер. На основании ЭТОЙ темы пришёл к выводу, что провести измерение можно с помощью библиотек Windows, опирающихся на тики процессора. Такое измерение ненадёжно, воспроизводимость результатов низкая, переносимость на другие машины не сравнимая.
Позже сравню алгоритмы на больших переборах, сравнивая целые секунды исполнения.Rioran
Роман, Москва, voronov_rv@mail.ru Яндекс-Деньги: 41001312674279
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
