Vanilla Lua - Combating too high numbers?

I am making an algorithm to calculate Lychrel numbers, and if you are too lazy to read, basically what I am doing is taking a number, and adding it to the reversed version of itself until it is a palindrome.
This is my code:

num = 295
while true do
 num = num+tonumber(string.reverse(tostring(num)))
 if num == tonumber(string.reverse(tostring(num))) then print(num) break end
end

Very short, and it works for most numbers, however if I put a number such as 295 or 196 it eventually errors because it turns num into a nil since it is too big. I am assuming that is what happens because the error is:


lua: random.lua:3: attempt to perform arithmetic on a nil value
stack traceback:
random.lua:3: in main chunk
[C]: ?

Is there any way to stop this from happening? Any help would be appreciated. Thanks!

I can't think of any way to get around this, other than building your own "datatype" for such large numbers.

You could save the value of your numbers as strings and write (maybe decimal) functions, that allow to add/reverse your strings.

But doing this with numbers like 196 won't be good for you, even if you use custom number formats/operators, since it'll start to take very very long

You could use the BigInt API (sorry, i got no link) from the forums. But after some time it will run out of memory.

and by very very long I mean like centuries long xD

Well I got bored, so I created a little thing, which should be able to solve your problem, although it is likely very slow compared to the ordinary way.

function add(str,str2)
  local newStr = ""
  local carry = nil
  local carry2 = 0
  for iStr = #str, 1, -1 do
    local lastNum1 = str:sub(iStr,iStr)
    local lastNum2 = str2:sub(iStr,iStr)

    lastNum1 = tonumber(lastNum1) ~= nil and lastNum1 or "0"
    lastNum2 = tonumber(lastNum2) ~= nil and lastNum2 or "0"

    local temp = tostring(tonumber(lastNum1)+tonumber(lastNum2))

    if #temp == 2 then
      carry = tonumber(temp:sub(1,1))
    elseif temp+(carry2 or 0) == 10 then
      carry = 1
      carry2 = nil
      temp = "0"
    else
      carry = nil
    end

    newStr = tostring(tonumber(temp:sub(#temp,#temp))+(carry2 or 0)) .. newStr

    if carry then
      carry2 = carry
      carry = nil
    else
      carry2 = nil
    end


  end
  if carry2 then
    newStr = carry2..newStr
  end
  return newStr
end

num = "295"
iter = 0
for i = 1, 1000 do
  num = add(num,string.reverse(num))
  sleep(.01)
end 
print(num)
print(tonumber(num))

I was lazy so it only supports adding numbers of equal length (which is what you are doing), and I only tested to make sure they were the same up to 43 iterations. I did a little test, and know it will go at least 200 more iterations, than adding the numbers together normally (didn't try any more than that as it took it a good 30sec to a min to do 1k iterations in a emulator).

The part at the bottom with the for loop is just the example of where I was testing the function to make sure it could go to 1k iterations.

note:

I got tired of trying to work out a bug half way through so I did a partial fix using the carry2 variable. If you feel like trying to fix it you can.

Here is my attempt. Works fine and as intended without weird partial fixes^^

function add(num1, num2)
    local bnum = "" --# shall become the longer string(number)
    local snum = "" --# shall become the shorter string(number)
    if(#num1 < #num2) then
        snum = num1:reverse() --# reverse, so the beginning is the least significant digit
        bnum = num2:reverse()
    else
        snum = num2:reverse()
        bnum = num1:reverse()
    end

    --# decimal addition digit by digit
    local result = ""
    local carry = 0
    for i = 1, #bnum, 1 do
        local first = tonumber(bnum:sub(i,i))
        local second = tonumber(snum:sub(i,i)) or 0
        local value = first+second+carry
        carry = math.floor(value/10)
        result = result..tostring(value%10)
    end
    --# last carry
    if(carry ~= 0) then
        result = result..tostring(carry)
    end

    --# reverse again, to get the most significant digit back to front
    return result:reverse()
end

If anyone wants to get it in fast, rather than readable, I would suggest getting rid of the double-reversal and reversing the loop(including last carry) instead.
That should make it faster. I just went for readability.

maybe, instead of sleep you could do

function sl()
os.queueEvent("wow")
os.pullEvent("wow")
end

It is faster I think

Running the following for like 10 minutes(2.6 GHz) on the Lua Console Standalone Interpreter with my add function I get to the last number in the series that has 10,000 digits, which is the 24,095th iteration of the loop:

i = 0
num = "196"
while #num <= 10000 do
    print(i, "#",#num,":",num)
    i = i +1
    num = add(num, num:reverse())
end

last output:

24095   #       10000   :     739467176810223174185372881707247433631423207412533463616576068267114396466605530946769129395403905128245580592032390126496348368359445503995626880989568738167711724049281923409583801348685900037113466102782989624636103825566138373112517241711864784084491457697699066006544531131257083614857636411364055067268224160251625409216687802488347453001049884282537761765190722501450609078196441941271042001760391479942631487467297414978028715248793254339988096684248117476007711462691259386233922175237114670722212694680272392328746514463683404688308538185019700315410265324080571708384598227559950186260889000448119794779712898879404966354595943136770540983787060860497903145947120265789655589641611319625678910909226008931139420085699014389200168442447281868779995799079730087419723433811016249555416997408702833327992618623133631661094990505300573525708585612787516392228076534714607607266317567581058690818758970522600243411354314835337466968141129580307332361323389153204620916760516532639204615076937683915779651820580298770784249510112594619483201185242859811496764069836097519306822046762687256878970571576032021284836579761730943867003136973552038319410883073068553750798389532071803338857620802995839320259147558476886563001099871874783947580006482223728315473227837466509848070242315725430244768093491825763662809579868509460349710211028092453084700265520757311113054975020238199290989664240749882328375565180562051067073996290269358728102448313118065761353121925589675061467745912573572212217170097513564883674115336191287148241684013053019785987281452038885319875140290023406763944151132422590234200750440161733898531210768373768005684464348248360362047885719008956988226171590291774566235538697255300399779192650650894077246657071629438137971673454219131716567493597199820984121945575516418439106730017742340862276276077071693617642511380030762409505121004681679095712565686838921900800457385433063683306813892086862576852512846039077910746992371275071760654721208169326075505076455759737000991566954128564727204469156917850113586598614186201975949500775304155188022017911690258846356138413844564350128473510187424302715211175383117255387736569946095619907649326232477881885814732758936281949728828577091525059130977722788651356499596969935532083700879226145725763001401545169796272021146204809740980696258706280866689337692856834521890935459114488045489318746391162512910710768775637886765273959495396080970226909627812377211550834064720646620144184969629902822958967430474595232096547464312344879732928773523154997398535644421917950861486770673328659131092281134978362523838045826538277269100778048053411278305316202359047935325409815102360305600101006198388533491617217432111492377128431325128033772424757518722203452006805261613904628112108454301983076009919257464581285227336130232108645980540921336110358202247549716403893899922356495294492727269083349814548593039019128698405968939377587840459164146864797075204979710214031862805828287400695121071118027511914213633880838215712502356312069506749577932903284167460929079820457132771411023755892714161899763123849513672051733773080905486051160013785177604419288219350417786906941610355012388572510736937206936820284466716514792271824714559960385249860571727419352852271878765532528671313202810625850424546705319458689047400597983202076011753024488191440664024297711440027984133307540789722134263370389877131029957461772553242256051287102532650475724175732297585050764347158365570280093669720080882828957405613591606531357312534133589878819916027135400549889878195009700564736330943474930308000075163004847266088643247507299969620141034543783658975626810503155242686552341157921466575244008925797295600747599759109858807977596314837496502783769960036707705560615052759126378261770850400820652283776471094389567174756087267286976951174016043584684950424025963757736136104532874945256218519499182618832011666211026069464928939912060363255061361632723270328861649948580229366048775780904013166609253667112790869172000634001901708050041445398430121318284569456423795598770248578735772179582177657037444599027771106751506034330192545335964001849961606376588149446268963489679895176696203724281478385762190793195007842890665351481326567746070610930160205558795907016554731029286154795472979045017304812783097408121759949373036219503710539880264598540683030137454620699587855611961930106070547765733075253565988248809502288092158682784093417391696672588976984369872653851785684596259048200360633545168523088263133357522800896444729656781196971277536785752967895598423555075372923012123893545240049807199200426100172859088310666362905672310399077577949564031975949056058833962328326164061552363042949788095247943394151667210237815291895014921662538479225510531747756270620423950586376439510482050768693761690557481676983489085677273247118094148167162883512056261506165496817629959967387315582349786457341396390810857996836007691697629900441486565118751143255686253550305107736579846378335440051916970003694742346890572648509272460000902040574339133626466097009501778989055004530620719014820748665532431854325596186405613659829279080917966400973175562762743466951475803237461537465156235200693149552253246377054760030031678993974252530227988145692331489830044018791331357144092884480870759872481229531365839886855023496645524158516009302313066935235566888073149253923727274958952483069966407419162308415606664493028628711640727105276883210553016040699787704152812883013516770443752726071979832583327337051166315959320366999152516198558420114068330764017980929065760393299328776057594960223563215206621739079326312518214829821071120497103692729598269020522007089402569697468963377717173400165869870593896930919939306735518053280873717284502504663218999389393717055742201863010633219144979546911232030533832483075475751919010669290192454911210826499406163497600254412291732275108411275076784124930684184111234821716184335894880710101006493064200419014512648749864201623492982103360750777110971682735738539837435262780531083191130856834375967684169148819213545634899071006386744965885969543213463645701232595474033669860317318926079382441015756027459447945221674307727008732069080604593860362567688846566868107109305262083756812984551785410854639089215527659226830466185256326588447179038007511552020182607872545104100367516541731879096391234548968695994654146888316780022059525191774728827950183628957337407589179874231524056699026480749075626793452821317536381519701866016255483722054355548304940553758851986119820219792550412477005950570201592405905585311058818751074391826465931448666190099747946554681494580524070812117546058171462184189648108798846503077696709187701189407713376459234594753997010229827686566306600976177499021615893376930984115246706496071769583562269143148709927602043813725575539221479118001706295764617230922454267279709471820678411107089059047047292977993003551696945531576368192996072621789659801016588849173963851743464486609768472768112134798338250153948102431986313242052448267714319992932569022488940254083752584112854162803568940693091533621367378476314701070722212165385229547764061466985638021354157570821312744201926962862102599380671040266180465573933179056932466990092901842020568461311113746025583072183405301966925006944163914768976007266367529184400767452924528612142080749014575727832374502926322295599986738387479169001100255688674964651862914037600298126747943298269135983898157344871299024607584141446726770309679348928167876727493119141675066179878651686267749129693014801627960467705108067142592102383926385211016051388067893185018146977619376740769526401837324724957728916501355807011909692734460582140770763633648413453114341996315168967808086850196764712662805805527435669832183725787216475906635266103495199391057236330226926189723339296914690704654842720108433237913793238009534669311901231645344861001894409907480915041128909523009108876527023106136985556987573020749641299884068960698280144967641250585464658513878899306978488020853999889161591949955831806373913516265389576450704268020580844703886514287363414647923393271977596212216087410632582228232694952086275117700673720852387581989933342398942506929780514682764795027339074184167100141062150244591727148666275243712765777734193477951100354742795197786721914516152962421773759461364103746747526281752131135444609570896807754095381378557217241725211372731665529401625436890387200575310640999576892004822950625240058127206772727865990078626600405543853972743705620984220305986541830518314484030867650135495674593520673859575716354336303812324027434742697179372491481321909770665036

Creator, on 19 April 2015 - 10:26 AM said:

maybe, instead of sleep you could do

 function sl() os.queueEvent("wow") os.pullEvent("wow") end 

It is faster I think

The original post was talking about "Vanilla Lua", so queuing events(which comes from computercraft) isn't necessary, since standard lua does not throw too long without yielding exceptions. You don't even have a sleep function in standard lua

Thank you InDieTasten! Your code works flawlessly :D/>
One question though,
in the line:

result = result..tostring(value%10)

Why do you have it be value modulo ten?
Shouldn't it just be value?

mrpoopy345, on 19 April 2015 - 01:22 PM said:

Thank you InDieTasten! Your code works flawlessly :D/>
One question though,
in the line:

result = result..tostring(value%10)

Why do you have it be value modulo ten?
Shouldn't it just be value?

If you take the numbers 15 and 17, my function iterates, from least significant to most significant digit:

5+7 = 12
12 modulo 10 = 2 <- and the carry is 1
so the "current" digit in this iteration should just be 2, otherwise the string would grow too many characters. the carry of 1 just gets added to the next digit:

1+1+1 = 3
3 modulo 10 = 3 <- and the carry is 0

so the first iteration results in 2
the second iteration results in 3
together they become 23, and reversing it at the and will get the final answer: 32 = 15+17

Hope that helped somewhat.

In other terms, my value variable holds the sum of the digits from the numbers and the carry from the operation before.
My value is then devided into the actual digit at that position, and the leftover carry for the next iteration.

The choice to use modulo comes just, because it was the first thing that got in my mind when writing. you could also convert the value to string, and read out the first character for carry, and the second character for the actual digit for the final result.

BTW, for those who are interested in the limitations:
This thing still does 80 calculations per second with 3.5k digits. Near 10k it slows down to 10 calcs/sec.

The "real" limit is, when the number of digits exceeds luas number capacity

Where do you get a standalone lua interpreter?

Creator, on 19 April 2015 - 09:42 PM said:

Where do you get a standalone lua interpreter?

Here. You can also use the online demo here.

Thanks, Lignum. Eat a +1