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

4096bits

  • Участник
  • *****
  • Публикации: 3238
    • Профил
Re: Точни корени?
« Отговор #15 -: Jun 09, 2015, 21:57 »
Не търся единствен корен, не търся и точен корен на някое число. Може и да няма. Ако няма точен корен, може да го представя и като сбор от точни корени, пък било то накрая и така.

big_integer = x^a + y^b + z^c + 14

Например.

А, ако може да е точен корен, още по добре. Например нещо от вида: big_integer = 5086283470**64625205.

Отделните множители ще са известни. Те също ще са степени на някое число. А big_one ще е тяхно произведение. Ако до десетине дена не намеря решение, ще се опитам да обясня, какво точно искам да постигна. Или да намеря някой математик от ТУ тук в София, да го видя, какво ще каже той.
Активен

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

neter

  • Global Moderator
  • Участник
  • *****
  • Публикации: 3408
  • Distribution: Debian, SailfishOS, CentOS
  • Window Manager: LXDE, Lipstick
    • Профил
    • WWW
Re: Точни корени?
« Отговор #16 -: Jun 09, 2015, 22:34 »
В такъв случай става още по-препоръчително да използваш метода за разлагане на прости множители. И щом предварително ще са ти известни някакви множители, то е по-добре да разлагаш тях, вместо после да мъчиш голямото число - така наизуст не съм сигурен по-какъв начин ще се отрази това на общото време за разлагане, но дори и да не доведе до спестено време, то поне ще доведе до спестена памет. И тук базата с известните прости числа (или само част от нея, ако не очакваш известните начални множители да надхвърлят някаква определена стойност) ще ти е от полза - трябва да се прави сравнение с нея преди всеки цикъл на разлагане на дадено число, което може да спести доста завъртания на цикли.
Активен

"Да си добре приспособен към болно общество не е признак за добро здраве" - Джиду Кришнамурти

romeo_ninov

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

...
Само за сведение опитай това:
Код:
man factor
Активен

0x2B|~0x2B

gat3way

  • Участник
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #18 -: Jun 09, 2015, 23:14 »
Ако не се търси корен квадратен, а просто целочислените делители, тогава има много подходи - доколко практични зависи от това с колко големи числа оперираш. Най-простият вариант е описан в уикипедия (с питонска имплементация):

http://en.wikipedia.org/wiki/Trial_division

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

"Knowledge is power" - France is Bacon

sharena_sol

  • Гост
Re: Точни корени?
« Отговор #19 -: Jun 10, 2015, 13:13 »
За целочислени делители има ефикасен алгоритъм, но трябва да имате под ръка квантов компютър  :).

За коренуване (с конкретен корен) може би е най-добре е с числени методи (Нютон примерно)
Активен

edmon

  • Гост
Re: Точни корени?
« Отговор #20 -: Jun 10, 2015, 14:23 »
ако искаш да разбереш дали числото 1341230917263912983714692837146239418732649182734 е някое друго число, което е повдигнато на някоя степен....
всъщност това ли е въпроса преди да продължа да умувам?
Активен

remotexx

  • Участник
  • *****
  • Публикации: 799
    • Профил
Re: Точни корени?
« Отговор #21 -: Jun 10, 2015, 21:00 »
т.е. само да уточня че тези ВСИЧКИТЕ са неизвестни - нали така: a,b,c,d=14,x,y,z
big_integer = x^a + y^b + z^c + 14

тогава така
I want to find the greatest integer less than or equal to the kth root of n
http://stackoverflow.com/questions/15978781/how-to-find-integer-nth-roots

напр big_integer=10 и (the greatest integer less than or equal to the kth root of n) = 8 = 2^3
то 10 = 2^3+2
11 = 2^3+3

те избираш n напр. = 2 и намираш най-близкото до него 2^P < big_integer
big_integer = 2^P + (big_integer - 2^P)
после може да продължиш аналогично за (big_integer - 2^P)
също така може и да пробваш с n=3 и т.н. докато ти писне или решиш че вече ползва прекалено много процесорно време...
Активен

4096bits

  • Участник
  • *****
  • Публикации: 3238
    • Профил
Re: Точни корени?
« Отговор #22 -: Jun 15, 2015, 19:41 »
ако искаш да разбереш дали числото 1341230917263912983714692837146239418732649182734 е някое друго число, което е повдигнато на някоя степен....
всъщност това ли е въпроса преди да продължа да умувам?
Да, основно искам да разбера, дали има начин да определя, някое число дали има точен корен, преди изобщо да търся базата и на какво е повдигната. Ако е, може да пробвам да ги търся.
Иначе голямото число, ще е прозиведение на степени на прости числа.
 Python-а малко ме обърка, ама днес по-рано го преборих. For loop не е като в С и се чудих по едно време що ми дава грешки  ;D. Нямах време до сега да се занимавам с въпроса, но половината програмка е готова.
Имам един въпрос относно Python. Как да сортирам dictionary, но според стойностите, не според ключа. Или сам трябва да си го напиша. То лесно ще хвърля всичко в нов речник, според някакви условия, но питам дали няма нещо готово. Мразя да губя време и да откривам топлата вода.
« Последна редакция: Jun 15, 2015, 19:45 от 4096bits »
Активен

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

PaperNick

  • Участник
  • *****
  • Публикации: 286
  • Window Manager: Xfce
    • Профил
Re: Точни корени?
« Отговор #23 -: Jun 15, 2015, 20:08 »
Имам един въпрос относно Python. Как да сортирам dictionary, но според стойностите, не според ключа.
https://docs.python.org/dev/library/collections.html#ordereddict-examples-and-recipes
Активен

За да вървиш напред, понякога се налага да започнеш отначало.

gat3way

  • Участник
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #24 -: Jun 15, 2015, 22:29 »
for цикъла е една от големите простотии в питон, защото всъщност for е итератор и оперира върху list-ове, някак тривиалното изпълнение с брояч и условие като в нормалните езици не е на почит и това е брутална простотия, особено за човек дето идва от C или подобен език. А за да е още по-забавно, тривиалният for цикъл в питон  - for counter in range(start,end) - всъщност създава списък от стойности между start и end и го пази в паметта и сега представи си как разликата между двете е няколко милиарда и изгърмяваш цялата физическа памет на машината с един прост цикъл. Да не говорим колко още по-глупаво е ако някъде в цикъла имаш условие и при достигането му, break-ваш, язък за разхищението на памет.

Та това е от първите неща, които човек научава - да ползва xrange вместо range, защото xrange е "генератор", т.е не се създава първоначално целия лист в паметта и после да се обхожда, а всеки елемент се генерира динамично. Обаче човек много скоро се научава да е мързелив, поради тази причина за "малки" цикли обикновено ползвам range, за "големи" цикли ползвам xrange.
Активен

"Knowledge is power" - France is Bacon

4096bits

  • Участник
  • *****
  • Публикации: 3238
    • Профил
Re: Точни корени?
« Отговор #25 -: Jun 15, 2015, 22:46 »
Гейт, мерси за това уточнение. Големия цикъл още не е дошъл, но скоро ще му дойде и на него времето.
Всъщност, реших, че не ми трябва да подреждам речника, ми само да нахакам в подобаващ ред ключовете един след друг, според стойностите им някъде, че да мога да ги обходя после.
Активен

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

gat3way

  • Участник
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #26 -: Jun 16, 2015, 00:17 »
Между другото. не знам какъв е казуса с твоя dict, но имам странното усещане че може би не ти трябва dict за да го реализираш това...щом ти трябва да сортираш по key-ове. Но не знам де.

Апропо, списъците в питон-а са много забавно нещо. Със съвсем леко усилие това се превръща в напълно функционален стек или опашка, в смисъл не е чак наготово, но с много малко усилия. Та ако реда на вкарване определя всичко, никакво малоумно сортиране не ти трябва, то и вероятно ще е бавно както повечето неща в този език :)

Но именно тоя момент с лесното организиране на разни FIFO/LIFO структури от данни като list - което в C обикновено троши нерви и време най-малкото заради memory management-а - много ми допада. Само няколко реда код и обикновено работи, трудно е да се изсереш отгоре даже.
Активен

"Knowledge is power" - France is Bacon

4096bits

  • Участник
  • *****
  • Публикации: 3238
    • Профил
Re: Точни корени?
« Отговор #27 -: Jun 16, 2015, 00:35 »
Ами така си написах функцията, защото така ми дойде на акъл. Трябваше да обходя едни неща и да им направя статистика, колко често се срещат във файла.
Та понеже отскоро се запознавам с питон, от три-четири дена и речника ми дойде най-подходящ като структура, а от де да зная, че трудно се подрежда. Одеве гледах за тези неща. Питат хората като луди. Та май ще ги извадя от речника и ще нахакам ключовете, според стойността във обикновен лист. То речника май и по индекс не можеш го достъпи.
А относно списъците ... ами да. Днес дори четох в едно pdf-че, че май си има тулче за тази работа. FIFO от обикновен списък или tuple. Изобщо май от всичко, дето може да му се приложи read() и write().
Реда на вкарване е произволен, защото входящите данни са такива. И като ги обхождам, само вдигам брояча-стойността, ако са в речника или просто добавям нов ключ със стойност 1. Ако ги няма там.

Код:
def sfreq(in_file):

f = in_file
freq = {}

for k in f:
if freq.has_key(k):
freq[k] += 1
else:
freq[k] = 1

return freq

Даже си мисля, че това else може да е излишно, но не съм пробвал. Дали ще вмъкне нов елемент, ако го махна?
Активен

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

gat3way

  • Участник
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #28 -: Jun 16, 2015, 01:26 »
Не мисля че речникът можеш да го индексираш. Ако нещата дето могат да се срещат не са ужасно много, аз бих обърнал нещата, бих си измислил хеш функция която да връща от нещото целочислена стойност в някакъв смислен range където да не страдаме толкова от колизии и тогава пак да си го организирам като списък, макар и с разхищения, просто понеже защото се индексира лесно и бързо...обаче това зависи от това колко възможни стойности можеш да индексираш и колко красива е хеш функцията. И пак има достатъчно неизвестни, та не знам дали е оптималното решение. Проблемът с подбирането на структурите данни, видиш ли. Според мен това е най-забавното нещо в дращенето на код като цяло и  е доста жалко че малоумната простотия с нечии добри практики и патърни се приема леко догматично - според мен без да е обременен с глупости, човек с времето сам си стига до изводите и решенията и после не мисли излишно.
Активен

"Knowledge is power" - France is Bacon

4096bits

  • Участник
  • *****
  • Публикации: 3238
    • Профил
Re: Точни корени?
« Отговор #29 -: Jun 16, 2015, 02:00 »
Сега, от този речник лесно може да се измъкнат за ушите първо ключовете с най-големи стойности и от там в низходящ ред и ще си дойде всичко на мястото. На мен ми трябват само ключовете подредени, според стойностите им, но не и самите стойности. Вече. Та май ще добавя в това още няколко реда и ще връща сортиран в низходящ ред ключове, според стойностите им, но вече ще е list. Имаше май някакви методи max и min, но за какво бяха. Толкова ми мина през главата. Малко блокирам вече и ще си дам два дена почивка от четенето.
Иначе в няма да се генерира прекалено голям списък в речника. Той ще е временен.
Или да видя как да го направя вместо с речник с tuples. Че там всичко може си блъскам. Малко ми бръмна главата от четене и нещо блокирам вече.
А иначе основния ми въпрос с корена... Няма да е лесно и няма да е сигурно нещо бързо работещо. Достатъчно бързо. И като гледам, няма само един начин, та ще трябва и правилен подход. Започва вече да ме интересува, не колко бързо ще го смята. Не чак толкова, а да е точно. Това е критично.
Активен

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