Автор Тема: Точни корени?  (Прочетена 29236 пъти)

romeo_ninov

  • Напреднали
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #60 -: Jun 19, 2015, 09:16 »
....
От друга страна са много по-трудни за генериране (е добре може да ползваш таблица с вече известните прости числа, но все пак имаш ограничение след което незнаеш следващото поред просто числа защото все още никой не го е открил)

Предполагам че нарастват по-бързо от степените на 2 но пък и предполагам можеш да измислиш друга редица, която нараства още по-бързо (незнам, примерно N**N**N**N...**N (N пъти) :) ) но къде е златния момент където една редица започва да нараства прекалено бързо за да е полезна, и къде е прекалено бавна - незнам.

Иначе да - трябва да е унифицирано представянето за това не споря.
Не мисля че са толкова трудни и ще се наложи да се ползват наистина големи числа. То това е и идеята на степените, да може да се генерира голямо число, което да има нужда от кратко "представяне" (запис). Иначе не знам от къде ми дойде идеята да са прости числа :)
Е как, и да не го е открил, ще циклиш числа нагоре и ще ги тестваш дали са прости, примерно с miller-rabin. Но това е прекалено теоретично - значи ако стигнеш дотам да ползваш толкова големи прости числа, че още никой да не ги е открил, значи ще имаш далеч по-големи проблем после да ги степенуваш така или иначе.
Ох, опрем ли до големи числа май ще е по-рационално просто да разрежем входния текст на приемливи по размер парчета, което да превръщаме индивидуално
Активен

0x2B|~0x2B

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #61 -: Jun 19, 2015, 10:48 »
То това ще се наложи, най-малкото защото изчислителните ни възможности не са безкрайни.

Аз също и не съм убеден че е добра стратегия да ходим в крайности с прекалено голям брой прости числа, които да повдигаме на степен (че и да стигнем до толкова големи, че да не са "открити" още). Определено ще се появят проблеми с това и те са свързани с начина по който кодираме "не вземай предвид тази степен". Дори само един бит да е достатъчен за целта (а аз не виждам как ще стане това лесно) - разхищенията въобще няма да са малки. Далеч по-изгодно става да описваш по-големи степени, отколкото да описваш много прости числа, чиято степен не вземаш предвид.
Активен

"Knowledge is power" - France is Bacon

4096bits

  • Напреднали
  • *****
  • Публикации: 6151
    • Профил
Re: Точни корени?
« Отговор #62 -: Jun 19, 2015, 10:50 »
Правилно! Записването на почти което и да е число като база и степен, заема по-малко памет, отколкото записа на самото число. Това е така дори за сравнително малки числа, като например 36. Което се представя двоично със 100100. Ако е със база и степен 110 10. Бит по-малко. Това е и идеята по-общо.
Употребата на прости числа се налага от самосебе си, но аз не мога да го обясня, така, че да ми допадне обяснението на мен самия, въпреки, че разбираз причината. Нямам знанията и езика за това.
Та ето какво се случва:
Текста просто се закодира като бази и степени.
Първо се взима текста и се определя честотата на срещаните вътре символи, за да може да се облекчат в последствие сметките.
Например името Бойко Борисов. Според честотата на срещане, се подреждат символите и в този ред.
'оБйкрв ис'
Всеки знак по своя ред в оригиналния текст се изразява като поредното просто число в редицата на всичките прости числа. Разбира се трябват ни само толкова, колкото е дължината на текста. Започва се от 2, 3, 5 и т.н.
Позицията на всеки знак от посланието, във подредения по честотата на срещане запис, се определя от степента.
Така буквата `o` като най-често срещана в случая, ще се представи като степен 1. Буквата `Б` ще се представя като степен 2. В предния си пост казах, че ще има и степен 0. Това нормално в един текст ще бъде интервалът, защото се среща най-често.
И Бойко Борисов се представя вече като бази и степени.
2^2х3^1х5^3х7^5х11^1х13^8х17^2х19^1х23^6х29^9х31=10х37^1х41^7
Дано някъде не съм сбъркал. Бях пропуснал в двишение знаците след интервала, та ги добавих. Но така стана и по-прегледно.
Полученото число е
15755314003698233343822284213372425367950000178844077447600722128478500L
И вече това число може да се представи самото то като база и степен, ако има точен корен. Ако няма, може да се представи като сбор от бази и степени.
При няколко страници текст или няколко мегабайта текст, целия вход може да се представи като сбор от бази и степени на половин ред тект, може би и по-малко. Ако имаме късмет да има точен корен, ще се представи просто като база, степен и това ще бъде всичко. Няколко, петнайситена или нека са тридесет напримен символа, за сметка на няколко мегабайта.
Това е целта. Проблема явно не е в кодирането, то е лесната част. Пуснах на мойта машинка 2 на степен 10 000 000 и го осметна за 57 и нещо секунди, като вероятно е ползвано само едното ядро. Цялото число като размер памет зае 3МВ. Това точно число, трябва да се представи така.

ххххх^nnnn + xxx^nnnnnn + nn^n + xxx^nn - 76

Например. Като запис е с нищожен размер.
По този начин може да се запише всичко. Ако са големи файлове, особено такива в които няма печатни символи, може би резулатта от кодирането ще е особено голямо число, което може и да не си представя. Но то също може да се представи по този начин.
Целия интернет, като обем информация, на теория може да се събере така на няколко реда или страница. Затова в предни постове споменах за Народната библиотека на две дискети. Не мога да пиша засега повече, че помагам на един приятел да се изнесе от апартамента.
« Последна редакция: Jun 19, 2015, 11:02 от 4096bits »
Активен

As they say in Mexico, "Dasvidaniya!" Down there, that's two vidaniyas.

4096bits

  • Напреднали
  • *****
  • Публикации: 6151
    • Профил
Re: Точни корени?
« Отговор #63 -: Jun 19, 2015, 10:53 »
То това ще се наложи, най-малкото защото изчислителните ни възможности не са безкрайни.

Аз също и не съм убеден че е добра стратегия да ходим в крайности с прекалено голям брой прости числа, които да повдигаме на степен (че и да стигнем до толкова големи, че да не са "открити" още). Определено ще се появят проблеми с това и те са свързани с начина по който кодираме "не вземай предвид тази степен". Дори само един бит да е достатъчен за целта (а аз не виждам как ще стане това лесно) - разхищенията въобще няма да са малки. Далеч по-изгодно става да описваш по-големи степени, отколкото да описваш много прости числа, чиято степен не вземаш предвид.

Допълнение заради предния пост на Гейт. В момента има достатъчно на брой открити прости числа, за да може да се кодира по описания вече начин една доста голяма част от каквото и да е. Трябва да имаме просто толкова на брой прости числа, колкото е дълъг файла. За да можем да заместим всяка позиция от файла с поредното просто число.

Макар че за изчислителните крайности май ще си прав. Трябва да се пробва просто.
« Последна редакция: Jun 19, 2015, 11:08 от 4096bits »
Активен

As they say in Mexico, "Dasvidaniya!" Down there, that's two vidaniyas.

romeo_ninov

  • Напреднали
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #64 -: Jun 19, 2015, 11:18 »
То това ще се наложи, най-малкото защото изчислителните ни възможности не са безкрайни.

Аз също и не съм убеден че е добра стратегия да ходим в крайности с прекалено голям брой прости числа, които да повдигаме на степен (че и да стигнем до толкова големи, че да не са "открити" още). Определено ще се появят проблеми с това и те са свързани с начина по който кодираме "не вземай предвид тази степен". Дори само един бит да е достатъчен за целта (а аз не виждам как ще стане това лесно) - разхищенията въобще няма да са малки. Далеч по-изгодно става да описваш по-големи степени, отколкото да описваш много прости числа, чиято степен не вземаш предвид.
Не знам дали един бит ще е достатъчно място за такъв флаг.  И аз се притеснявам повече за разделителя между степените, защото него ще трябва да го ползваме независимо дали има степен или не.
А ако вземем идеята ти за многовариантността можем да подберем големи степени на големи числа, което си мисля че ще съкрати тоталната дължина на изходния текст

Правилно! Записването на почти което и да е число като база и степен, заема по-малко памет, отколкото записа на самото число. Това е така дори за сравнително малки числа, като например 36. Което се представя двоично със 100100. Ако е със база и степен 110 10. Бит по-малко. Това е и идеята по-общо.
Употребата на прости числа се налага от самосебе си, но аз не мога да го обясня, така, че да ми допадне обяснението на мен самия, въпреки, че разбираз причината. Нямам знанията и езика за това.
....
Хм, трябва много да внимаваш с честотния анализ и разбиването на двоично дърво. Такова прекодиране може да има доста негативен резултат ако го прилагаш върху данни с голяма ентропия. Може примерно да се наложи да ползваш 13-14 бита за да кодираш текст от 100 символа вместо 7 бита константен размер.
Активен

0x2B|~0x2B

Naka

  • Напреднали
  • *****
  • Публикации: 3395
    • Профил
Re: Точни корени?
« Отговор #65 -: Jun 19, 2015, 11:41 »
Целия интернет, като обем информация, на теория може да се събере така на няколко реда или страница. Затова в предни постове споменах за Народната библиотека на две дискети.

Излишъка от информация при обикновенният език е доста голям. За Аглийският език сметките бяха, че количеството информация е около 2 бита на буква.

Т.е. ако една буква се кодира в ASCII (127) това са 7бита.
максималната компресия която теоретично може да се постигне тогава ще бъде 7/2 = 3.5




Активен

Perl - the only language that looks the same before and after encryption.

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #66 -: Jun 19, 2015, 11:52 »
Славянските езици в писмена форма на кирилица имат доста по-висока ентропия от английския, едно защото азбуката описва почти всеки звук и две защото по принцип не си позволяваме излишъци. Не сме като онзи свещеник в градската легенда за френския език, дето измислил писмената форма на езика под влиянието на тънкия момент че му плащали за написан символ.

Въпреки че тази цялата схема със степените ако се окаже работеща, не виждам какво общо има изобщо с ентропията на входните данни, то това е забавното в цялата работа.
Активен

"Knowledge is power" - France is Bacon

4096bits

  • Напреднали
  • *****
  • Публикации: 6151
    • Профил
Re: Точни корени?
« Отговор #67 -: Jun 19, 2015, 12:02 »
Работеща е и ентропията няма никакво значение.
Активен

As they say in Mexico, "Dasvidaniya!" Down there, that's two vidaniyas.

romeo_ninov

  • Напреднали
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #68 -: Jun 19, 2015, 12:04 »
Славянските езици в писмена форма на кирилица имат доста по-висока ентропия от английския, едно защото азбуката описва почти всеки звук и две защото по принцип не си позволяваме излишъци. Не сме като онзи свещеник в градската легенда за френския език, дето измислил писмената форма на езика под влиянието на тънкия момент че му плащали за написан символ.

Въпреки че тази цялата схема със степените ако се окаже работеща, не виждам какво общо има изобщо с ентропията на входните данни, то това е забавното в цялата работа.
Аз отворих сума за ентропията, защото по-горе 4096bits отвори дума за двоично дърво и честотен анализ на текста. Иначе да, наистина няма нищо общо с метода, който мислим :)
Целия интернет, като обем информация, на теория може да се събере така на няколко реда или страница. Затова в предни постове споменах за Народната библиотека на две дискети.

Излишъка от информация при обикновенният език е доста голям. За Аглийският език сметките бяха, че количеството информация е около 2 бита на буква.

Т.е. ако една буква се кодира в ASCII (127) това са 7бита.
максималната компресия която теоретично може да се постигне тогава ще бъде 7/2 = 3.5
по спомени е 5 и нещо бита на буква (английския), но това би имало значение само ако искаме предварително да обработим входящия текст за да намалим дължината му
Работеща е и ентропията няма никакво значение.
Работеща е ако можеш да се справиш с факторизация на големи числа (в обозримо време). Ама тогава ще можеш директно да разбиваш (примерно) RSA ключове :)
Активен

0x2B|~0x2B

4096bits

  • Напреднали
  • *****
  • Публикации: 6151
    • Профил
Re: Точни корени?
« Отговор #69 -: Jun 19, 2015, 12:25 »
Не съм споменал двоично дърво. Само показах, че представянето на число като база и степен, заема по-малко памет, от записа на самото число.
Кодирането и разкодирането работят. Пробвал съм го. Няма грешка и няма откъде да има. Прекалено прост е метода. Тези двете са лесните задачи. Представянето на резултата като база и степен или сбор на такива е трудната. Имам позната в БАН, може би ще може да ме свърже с някой математик. Ако алгоритмите, които съм насвалял нещо ме затруднат.
Активен

As they say in Mexico, "Dasvidaniya!" Down there, that's two vidaniyas.

Naka

  • Напреднали
  • *****
  • Публикации: 3395
    • Профил
Re: Точни корени?
« Отговор #70 -: Jun 19, 2015, 12:28 »
Въпрос:
Ако входните данни (текста,числото и т.н.) са бял шум - Абсолютно случайни битове и равномерно разпределени - ще може ли това да се смачка?

Според мен не.
И колко числа са именно такива - изглеждат като шум.
Сега тънкият момент е че ако успееш да видиш (или намериш) някъкъв патън, някакъв излишък от информация, някаква структура в този шум
то явно и той може да се смачка.

например може да се успее да се разложи едно число на някакви коефиценти.....Ама да не се укаже че в общият случай - за случайно избрани числа, групичката от тези коефиценти ще се получи точно толкова дълга колкото и оригиналното число?

Активен

Perl - the only language that looks the same before and after encryption.

romeo_ninov

  • Напреднали
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #71 -: Jun 19, 2015, 12:39 »
Не съм споменал двоично дърво. Само показах, че представянето на число като база и степен, заема по-малко памет, от записа на самото число.
...
Спомена по-горе. Примера с името на премиера е честотен анализ. И след това представянето на символите в зависимост от честотите е двоично дърво
Въпрос:
Ако входните данни (текста,числото и т.н.) са бял шум - Абсолютно случайни битове и равномерно разпределени - ще може ли това да се смачка?

Според мен не.
И колко числа са именно такива - изглеждат като шум.
Сега тънкият момент е че ако успееш да видиш (или намериш) някъкъв патън, някакъв излишък от информация, някаква структура в този шум
то явно и той може да се смачка.

например може да се успее да се разложи едно число на някакви коефиценти.....Ама да не се укаже че в общият случай - за случайно избрани числа, групичката от тези коефиценти ще се получи точно толкова дълга колкото и оригиналното число?
Според мен би трябвало да може да се компресира. Иначе въпроса с изходния текст и неговата дължина е резонен. И аз си мисля че ще има входни текстове, които няма да може да се представят с по-къс изходящ текст, но не мисля че това ще зависи от ентропията. Защото ние дискутираме просто различно представяне на входящия тескт. И факта че (понякога) изходния текст ще е по-къс от входния т.е. ще имаме форма на компресия не зависи (според мен) е само страничен ефект от метода на представянето
И ако се върнем на алегорията на gat3way за компресирането не трябва да забравяме че ние внасяме енергия в системата и по този начин променяме (в една или друга посока) ентропията на изследваната система :D
Активен

0x2B|~0x2B

4096bits

  • Напреднали
  • *****
  • Публикации: 6151
    • Профил
Re: Точни корени?
« Отговор #72 -: Jun 19, 2015, 13:12 »
Ами начина на кодиране вече го знаете. Направете опит. :)
Резултатът в крайна сметка ще е един и същ. Голямо число. И тук вече се стига до представянето му.
« Последна редакция: Jun 19, 2015, 13:22 от 4096bits »
Активен

As they say in Mexico, "Dasvidaniya!" Down there, that's two vidaniyas.

Naka

  • Напреднали
  • *****
  • Публикации: 3395
    • Профил
Re: Точни корени?
« Отговор #73 -: Jun 19, 2015, 13:23 »
Не сме като онзи свещеник в градската легенда за френския език, дето измислил писмената форма на езика под влиянието на тънкия момент че му плащали за написан символ.
Любимият ми френски спелинг е:

Jacqueline (10) vs Жаклин (6)
Активен

Perl - the only language that looks the same before and after encryption.

romeo_ninov

  • Напреднали
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #74 -: Jun 19, 2015, 13:26 »
Не сме като онзи свещеник в градската легенда за френския език, дето измислил писмената форма на езика под влиянието на тънкия момент че му плащали за написан символ.
Любимият ми френски спелинг е:

Jacqueline (10) vs Жаклин (6)
Има и с по-голям коефициент на "компресия" :P
renault - рено (7/4)
peugeot - пежо (7/4)
Активен

0x2B|~0x2B