Изпечатай

[4096bits]

Не съм математик и искам да питам, дали някой знае начин за определяне на това, дали някое число има точен корен? Все тая квадратен или n-ти.

Да допълня, че става въпрос за много големи числа. От порядъка на 300 000 знака до много повече. За проба само записах стойността на едно такова число във файл, който стана 3 МВ голям.

[sharena_sol]

И аз не съм математик, но ми стана интересно и се порастърски из интернет:

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

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

[4096bits]

Ами и аз попаднах на това, а и на още доста неща, включително и на едно wiki с алгоритми на всякакви езици, но при положение, че за изчисленията ще трябва време, си помислих, дали няма да е по-бързо, ако просто насека числото с два милиона цифри на парчета и да го направя за всяко. Но искам и да мога да определя, дали някое от тях има точни корени. Да елиминирам неподходящите.

[Odido]

Без да съм математик ,нито програмист ,но елементарна проверка с един иф от рода на:
ако след коренуването на i  резулата е integer ,да връща true , няма ли да стане?

[romeo_ninov]

Без да съм математик ,нито програмист ,но елементарна проверка с един иф от рода на:
ако след коренуването на i  резулата е integer ,да връща true , няма ли да стане?

А замисляш ли се за сложността на коренуване на число с милиони цифри?

Иначе разбиване на прости множители и следене дали има по четно число от тях е приложим метод

[4096bits]

Целта ми е, да мога да определя, дали числото има точен корени и едва тогава да ги търся.
Елементарно може да се отхвърлят някои числа, като просто се погледне последната цифра. Всички степени завършват на  0, 1, 4, 5, 6, 9.

Odido, целта ми е да избегна точно това изчисление, ако ще е по-бавна тази проверка от проверката дали изобщо числото има точен корен. Ама това не зная, как да направя тази проверка.
Иначе лесно мога да го пусна да се проверява, дали ще е равно на n-та степен на нещо. Ама това, ако го правя, ще трябва да го правя за също толкова безумно много числа. За всяко от тях.
Ако не зная, че 10 000х10 000 е 10 000 000 000, за да проверя кой е корена на 10 000 000 000, няма да искам да умножавам всичко на себе си от 2 нагоре, докато стигна до 10 000. Това ще е бавна проверка. Искам точно нея да избегна.
А сметките са си бавни. Повдигнах за проба 2 степен 10 000 000 и го смята малко под минута. Не търсих как да му кажа, да смята с повече от едно ядро.
Май ще трябва да търся някакъв вариант с GPU, а там ще ми е мътна...

[Odido]

То другия вариант в този случай ,който ми хрумва е с факторизация ,еднакво неефективен също.За паралелното смятане Gateway ,май няма кой да го стигне тук.Hashkill е чудесен негов пример.

[neter]

Никой от по-познатите методи за намиране на корен не е ефективен за такива големи числа. Но, както и romeo_ninov предложи, аз бих го пробвал първо как върви с разлагане на прости множители, като обаче (ако нещо не се оплитам в мислите си) не съм съгласен, че трябва да се следи за четен брой от множители, а трябва да се следи за съответни на степента на корена бройки от еднакви множители. Опростен пример с корен пети от 7776:

nthroot(7776, 5) = nthroot(2*2*2*2*2*3*3*3*3*3, 5) = nthroot(2*2*2*2*2, 5) * nthroot(3*3*3*3*3, 5) = 2*3 = 6

Присъствието дори на една група от еднакви множители, броят на които не отговаря на степента на корена, води до липсата на целочислен корен.

Правилно си забелязал, че всички степени завършват на 0, 1, 4, 5, 6 и 9, но при четни степени. Ползвай го, за да отсяваш някои от числата, които ти се налага да смяташ. Не съм сигурен някаква проверка за това дали числото не е просто дали няма да доведе до някакъв положителен ефект в отсяването, или само ще внесе допълнително забавяне, но може без изчисление да се пробва поне сравнение с база от текущо известните прости числа, ако твоето не е по-голямо от най-голямото, открито досега - 2^57,885,161 − 1

[romeo_ninov]

Никой от по-познатите методи за намиране на корен не е ефективен за такива големи числа. Но, както и romeo_ninov предложи, аз бих го пробвал първо как върви с разлагане на прости множители, като обаче (ако нещо не се оплитам в мислите си) не съм съгласен, че трябва да се следи за четен брой от множители, а трябва да се следи за съответни на степента на корена бройки от еднакви множители. Опростен пример с корен пети от 7776:

nthroot(7776, 5) = nthroot(2*2*2*2*2*3*3*3*3*3, 5) = nthroot(2*2*2*2*2, 5) * nthroot(3*3*3*3*3, 5) = 2*3 = 6

....

Съгласен. Аз приемам (не знам защо) че говорим само за квадратен корен/степен. От там и дефинирането ми за четни/нечетни степени на простите множители

[4096bits]

Предполагам проблема е, че ми липсват основни знания за числата.
И то основно за простите числа, което е по-важното. Иначе голямото число е произведение на много множители - няма как да е просто. Ще потърся още инфо в нета и ще видя, какво ще правя. Изглежда не е прост въпрос, който ей така да намери отговор. Преди време исках да се позанимавам с това, дето сега ми се върти в главата, но тогава машините бяха порядъци назад от това, което ми беше нужно. Сега са 64 битови, многоядрени. Ама малко почват да ме гризат съмнения отново. Ще видим. 

Коренът изобщо не е квадратен. Може 4954-ти например на 6816888133548165668417941006778464
Това последното е малко. Сложете още няколко хиляди цифри след последната.

[neter]

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

Гледаме числото, на което търсим корен, отзад напред. Първо се прави проверка дали първата (реално последната) цифра е 0, 1, 4, 5, 6 или 9. Ако не е, то числото няма целочислен корен. Ако е, продължаваме нататък. Намираме цифра, степента на която завършва на първата цифра от числото, на което търсим корен. Запазваме си наум първата цифра от степента на намерената цифра. Ако намерените цифри са повече от една, запазваме си наум всички първи цифри на степените им. След това умножаваме първата и втората цифра на числото, на което търсим корен, полученото число го умножаваме по 2 и резултатът го сумираме със запазената наум цифра, след което проверяваме дали последната цифра от резултата е 0, 1, 4, 5, 6 или 9. Ако запазените наум цифри са били повече от една, правим отделни проверки за сума с всяка от тях поотделно. Ако няма резултат, завършващ на някоя от търсените цифри, то методът не може да даде гаранция, че има целочислен корен на търсеното число. Ако има подходящ резултат, продължаваме нататък, като си запазваме наум първата цифра от умножението на първата и втората цифра, но само ако е двуцифрено, иначе 0. Умножаваме втората и третата цифра от числото, на което търсим корен, сумираме го със запазената наум цифра и последната цифра от резултата отново ще ни покаже дали да продължим напред, или методът не дава гаранция за това число. Ако продължаваме, то правим същата проверка за резултата от третата и четвъртата цифра от числото, на което търсим корен, ползвайки наум първата цифра от предходното умножение (на втората и третата цифра), и така нататък за всички цифри на числото. Ако методът работи, то успешното обхождане на всички цифри на числото ще ни даде гаранция, че даденото число има целочислен корен, като неуспешното обхождане не е показател за това дали числото има целочислен корен, или не.

Пример:
Търси се sqrt(343396) и гледаме числото отзад напред.
6 е коректна цифра, т.е. е една от 0, 1, 4, 5, 6 и 9
6*6 = 36; последната цифра от резултата съвпада с първата цифра на числото, запазваме наум 3
9*6 = 54; 54+54+3 = 111; последната цифра е коректна и запазваме наум 5
3*9 = 27; 27+27+5 = 59; последната цифра е коректна и запазваме наум 2
3*3 = 9; 9+9+2 = 20; последната цифра е коректна и запазваме наум 0
4*3 = 12; 12+12+0 = 24; последната цифра е коректна и запазваме наум 1
3*4 = 12; 12+12+1 = 25; последната цифра е коректна
Успешното обхождане на цифрите показва, че числото има точен корен.

При възникване на комбинация от свободно време и муза ще го разиграя по-стабилно при мен (стига да не го забравя пак), но ако на някой му е интересно и има възможност, да действа. Нямам идея дали няма да се окаже пълна глупост, или дали всъщност не съществува подобен метод отдавна, както и въобще не съм го мислил какво ще е положението с неквадратни корени, но... поне да споделя

[4096bits]

Ще го видя и аз. То начини не е като да няма сигурно. Просто се чудя, може да се случи в разумно време. Благодаря!
Като го направя, ще споделя, за какво ми е.

[neter]

Ще го видя и аз.

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

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

П.П.: Чакам с нетърпение да кажеш за какъв дявол ги смяташ тези корени, че ми стана любопитно още когато спомена за сметки с големи числа в темата за OpenCV

[remotexx]

Колега..
да беше дал по-подробна информация или един пример барем... че ми стана интересно
Търсиш да има единствен корен, всички възможни, или някой конкретен (min, max)?
напр. 16 = 2^4, 4^2 т.е. в общия случай имаме Min, Max и/ли цяло мнонжество от решения


http://stackoverflow.com/questions/15978781/how-to-find-integer-nth-roots
алгоритъма е тук
http://en.wikipedia.org/wiki/Nth_root_algorithm

или gmpy2.iroot, gmpy2.isqrt
http://stackoverflow.com/questions/27607711/check-if-an-integer-has-perfect-nth-root-python

[romeo_ninov]

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

не винаги. С много голяма вероятност, но не винаги Все ще се намерят сред тях и прости и точни квадрати и произведение на две прости числа.