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

romeo_ninov

  • Участник
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #45 -: Jun 17, 2015, 16:47 »
Мне, степени на две са ти бинарното число. Докато аз искам да играя с прости числа ( и неограничено число за степен).
Аз ползвах bc:

Код:
2^1001+3^1002+5^1003+7^1004
30090691925576896817762391525509448290021291652694477976838515130578\
50401758032175543096625694980013524398768228433773781226754037108985\
17651059802804979798484768641976994743857560231992664435245802456382\
24952238359797965144201922557281638378500540605675478022200061990959\
73912866172604361235340039603572959111685943913091130339534177547013\
17843801520417515248539351050470639392268748190736100952871290555680\
91121435476459597060793717288212898190929204165393698894492370374504\
21096019618874106997455906221489617420153364251120374225290721015378\
73657660270761184997490019018360201880218486096430110214122064160885\
68746471420401373365626640199969463405839927493038591480628621739250\
54881655693817009942449102429948644377952846221222565802991556417518\
72970391706917530334627032421438448735142261070333009765236602176970\
314664389375273450412548052549287
Активен

0x2B|~0x2B

gat3way

  • Участник
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #46 -: Jun 17, 2015, 16:54 »
Дам, ясно е къде е разминаването.

Значи все пак остава проблема с намирането на въпросните степени. Всъщност, за да е по-забавно, според мен с голяма вероятност тази задача има повече от едно решение и на нас ни трябва най-оптималното.
Активен

"Knowledge is power" - France is Bacon

Naka

  • Участник
  • *****
  • Публикации: 2655
    • Профил
Re: Точни корени?
« Отговор #47 -: Jun 17, 2015, 17:07 »
Може да го опростим още, да търсим полином от вида Н = 2^x + y

a=2**n1+3**n2+5**n3.......
H=2**n1+3**n2+5**n3.... + y

А не е ли ключа от бараката в остатъка +y

Независимо как се разлага числото, да се търси най-близката стойност до оригиналното число и след това само да се прибави остатъка y така че да стане същото.

Обаче полинома трябва така да се намери че да бъде възможно най-близък до оригиналното число т.е. y да бъде възможно най-късичък. щото ще трябва и y-то да съхраним.
ще е много интересно ако се намери такова разложение че y да бъде 1, 3... 17,.... 50, ..12345, ....0
« Последна редакция: Jun 17, 2015, 17:21 от Naka »
Активен

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

romeo_ninov

  • Участник
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #48 -: Jun 17, 2015, 17:14 »
Дам, ясно е къде е разминаването.

Значи все пак остава проблема с намирането на въпросните степени. Всъщност, за да е по-забавно, според мен с голяма вероятност тази задача има повече от едно решение и на нас ни трябва най-оптималното.
О, да, това с повече от едно решение е вярно. Но си мисля че е малко вероятно. И (си мисля) най-оптималното (от гледна точка на изходния текст) е да се търси такова с максимална степен в най-старшите степени. Така ще се намалят степените на младшите степени
Активен

0x2B|~0x2B

romeo_ninov

  • Участник
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #49 -: Jun 17, 2015, 17:16 »
...

А не е ли ключа от бараката в остатъка +y

....
Към остатъка можем да приложим същия алгоритъм докато получим остатък < от най-високата степен. Което ще е приемливо за съхранение
Активен

0x2B|~0x2B

gat3way

  • Участник
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #50 -: Jun 17, 2015, 17:21 »
Виждам и още един проблем, но той е с представянето и не е огромен. За да има задачата решение, ще трябва да позволим нулевата степен, тоест да добавяме 1. В противен случай много лесно мога да дам примери за числа, които не могат да се разложат на сбор от степенувани прости числа. Но ще трябва да измислим и как да кодираме нулева степен и как да кодираме "степен която не вземаме предвид",
Активен

"Knowledge is power" - France is Bacon

romeo_ninov

  • Участник
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #51 -: Jun 17, 2015, 17:24 »
Виждам и още един проблем, но той е с представянето и не е огромен. За да има задачата решение, ще трябва да позволим нулевата степен, тоест да добавяме 1. В противен случай много лесно мога да дам примери за числа, които не могат да се разложат на сбор от степенувани прости числа. Но ще трябва да измислим и как да кодираме нулева степен и как да кодираме "степен която не вземаме предвид",
Мда, може да имаме 2**1+3**0+0*(5**0)+7**2 (само пример)
Но това е малка грижа, само пакетиране. Също трябва да се помисли и за разделителя между степените :)
Активен

0x2B|~0x2B

4096bits

  • Участник
  • *****
  • Публикации: 3239
    • Профил
Re: Точни корени?
« Отговор #52 -: Jun 17, 2015, 17:30 »
Радвам се, че ви стана интересно. Само да се прибера и да седна да почина малко и ще напиша точно за какво става въпрос. Има я и нулевата степен.
Активен

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

remotexx

  • Участник
  • *****
  • Публикации: 799
    • Профил
Re: Точни корени?
« Отговор #53 -: Jun 17, 2015, 21:26 »
хехех ще трябва да почакаме още маалко - докато няколко Кю-бита станат по няколко цента единия и тогава вече ще е лесно, но колкото по-наближаваме границата ще става и по-трудно
https://en.wikipedia.org/wiki/Pareto_efficiency

Едно време wavelet компресията ми се струваше бавна, вече не чак толкова..
Активен

gat3way

  • Участник
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #54 -: Jun 18, 2015, 00:41 »
Не задължително. В смисъл не отхвърлям възможността някоя голяма математическа глава да измисли хитър алгоритъм по който въпросната операция да стане напълно практична с наличния хардуер за прилично големи входни стойности. Все пак такива неща се случват, макар и бавно с други подобни проблеми, примерно факторизацията на целочислени стойности. Всъщност, въпросната наша постановка е напълно реална и възможна и в момента с "тривиални" методи - просто не за толкова големи стойности колкото би ни се искало, за да можем да намажем достатъчно ефективна компресия.

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

Идеята че въпросното "компресиране" може да стане по съвсем различен начин - демек ние ще позволим материята да се "компресира" достатъчно много че да започне не само термоядрена реакция, ами и нещото да се видоизмени и да заприлича на някаква мини неутронна звезда примерно - и от това нещо по желание да възтановим точно първоначалната конфигурация от песъчинки и силно разреден газ само защото сме открили някакви чисто математически съотношения между някакви параметри на тази система и въпросните съотношения са далеч по-сбити от информацията за възможните конфигурации на атомите и техните връзки в молекулите, е забавна идея. Звучи като някаква доста грозна математическа перверзия. Това религиозните хора ще го намразят, защото ще се окаже че сме по-добър Господ от техния Господ и можем по-ефективно да организираме там божествената реалност.


В смисъл аз поне много обичам да си обяснявам нещата с аналогии, а не съм физик за да правя точно такива аналогии, но пък и не се сещам за някаква по-добра в момента, така че се извинявам ако цялото това изглежда доста нелепо.
« Последна редакция: Jun 18, 2015, 00:47 от gat3way »
Активен

"Knowledge is power" - France is Bacon

romeo_ninov

  • Участник
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #55 -: Jun 18, 2015, 15:21 »
...
В смисъл аз поне много обичам да си обяснявам нещата с аналогии, а не съм физик за да правя точно такива аналогии, но пък и не се сещам за някаква по-добра в момента, така че се извинявам ако цялото това изглежда доста нелепо.
Ти изби рибата и разката мамата на ентропията :D.
Иначе има добра идея в думите ти (аз също не съм физик). Но в горната идея (според мен) не играем с ентропия въобще. Ние просто сменяме представянето на числото (входящия текст). И се опитваме да намерим такова представяне, което да може да се представи с много по-малко симвили (и наричаме това компресия).
Активен

0x2B|~0x2B

sharena_sol

  • Гост
Re: Точни корени?
« Отговор #56 -: Jun 18, 2015, 16:06 »
Мне, степени на две са ти бинарното число. Докато аз искам да играя с прости числа ( и неограничено число за степен).

Добре де но какво е предимството на простите числа в този случай. Те са точно толкова на брой колкото и Естествените числа и в този контекст не са с нищо по-специални (виж ако беше разлагане на прости множители е друго, но при полиномите не виждам с какво са по-различни от кои да е други цели изброими положителни числа - примерно степените на 2)

Ако разбирам идеята е да изберете някакъв "базис" и да представяте данните като координати/вектор в този "базис" макар че в случая един и същи вектор има повече от едно преставяне като полином примерно така че не е баш линейно пространство.

Примерно полином с допустими коефициенти 0 или 1ца и "базис" степени на двойката си е точно както и ти казваш бинарното представяне на това число/данни ( и в случая има единствено представяне) но ако искаш да покриеш цялото пространство (всички възможни числа) то тогава не правиш никаква компресия, а просто си го записваш с нули и единици (както си се записва и сега в паметта/диска-а).

Струва ми се че какъвто и друг "базис" да избереш ситуацията ще е подобна.

Имам спомен преди време, че съм чел за подобен подход при, който обаче имаш таблица на най-често срещаните (статистически спрямо домейна на приложение) компоненти и тях ги енкодваш с по-малко битове, за сметка на по-рядко срещаните. В най-лошия случай нямаш голяма полза, но пък средно печелиш нещо.
« Последна редакция: Jun 18, 2015, 16:09 от sharena_sol »
Активен

romeo_ninov

  • Участник
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #57 -: Jun 18, 2015, 16:15 »
Мне, степени на две са ти бинарното число. Докато аз искам да играя с прости числа ( и неограничено число за степен).

Добре де но какво е предимството на простите числа в този случай. Те са точно толкова на брой колкото и Естествените числа и в този контекст не са с нищо по-специални (виж ако беше разлагане на прости множители е друго, но при полиномите не виждам с какво са по-различни от кои да е други цели изброими положителни числа - примерно степените на 2)
...
Дребното предимство е че изрязвам голяма част от многовариантността и имам уникалност на основите. Освен това скоростта на нарастване на простите числа е по-голяма.
Вярно е че има варианти и за по-къси записи. Например 18446744073709551615 има доста къс запис (264-1)
Но крайната идея е да имаме унифициран метод за запис, който да е много по-кратък (статистически)
Активен

0x2B|~0x2B

sharena_sol

  • Гост
Re: Точни корени?
« Отговор #58 -: Jun 18, 2015, 18:35 »
Мне, степени на две са ти бинарното число. Докато аз искам да играя с прости числа ( и неограничено число за степен).

Добре де но какво е предимството на простите числа в този случай. Те са точно толкова на брой колкото и Естествените числа и в този контекст не са с нищо по-специални (виж ако беше разлагане на прости множители е друго, но при полиномите не виждам с какво са по-различни от кои да е други цели изброими положителни числа - примерно степените на 2)
...
Дребното предимство е че изрязвам голяма част от многовариантността и имам уникалност на основите. Освен това скоростта на нарастване на простите числа е по-голяма.
Вярно е че има варианти и за по-къси записи. Например 18446744073709551615 има доста къс запис (264-1)
Но крайната идея е да имаме унифициран метод за запис, който да е много по-кратък (статистически)

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

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

Иначе да - трябва да е унифицирано представянето за това не споря.
Активен

gat3way

  • Участник
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #59 -: Jun 19, 2015, 08:51 »
Е как, и да не го е открил, ще циклиш числа нагоре и ще ги тестваш дали са прости, примерно с miller-rabin. Но това е прекалено теоретично - значи ако стигнеш дотам да ползваш толкова големи прости числа, че още никой да не ги е открил, значи ще имаш далеч по-големи проблем после да ги степенуваш така или иначе.
Активен

"Knowledge is power" - France is Bacon