SHOW ME WHAT YOU GOT. [Show off your project!]

Nov 19 2015, 12:09 pm
Bravo1	Wacky Waving Inflatable Arm Flailing Tube Man!

Nov 19 2015, 1:34 pm (Edited on Nov 19 2015, 2:12 pm)

Popisfizzy

And here's a similar couple of tests as before, but for subtraction now. The first one is 30 randomly-generated, 4,000 hex digit (~4,800 decimal digit) numbers being subtracted.

                         Profile results (total time)
Proc Name                       Self CPU    Total CPU    Real Time        Calls
---------------------------    ---------    ---------    ---------    ---------
/mob/verb/Subtract_Test1           0.000        0.450        0.450            1
/pif_BigInt/proc/Subtract          0.153        0.450        0.450           30
/pif_BigInt/proc/Set               0.074        0.169        0.169           30
/pif_BigInt/New                    0.000        0.169        0.169           30
/pif_BigInt/proc/_GetBlock         0.100        0.117        0.124        90030
/pif_BigInt/proc/_SetBlock         0.087        0.107        0.113        60090
/pif_BigInt/proc/Length            0.036        0.038        0.060       150285
/pif_BigInt/proc/LargestBit        0.000        0.000        0.000           30
/pif_BigInt/proc/Expand            0.000        0.000        0.000           45
/pif_BigInt/proc/Contract          0.000        0.000        0.000           36
/pif_BigInt/proc/Sign              0.000        0.000        0.000           60

And the difference of two randomly-generated, 24,000 hexadecimal digit (~29,000 decimal digit) integers.

                         Profile results (total time)
Proc Name                       Self CPU    Total CPU    Real Time        Calls
---------------------------    ---------    ---------    ---------    ---------
/mob/verb/Subtract_Test2           0.000        0.095        0.095            1
/pif_BigInt/proc/Subtract          0.037        0.095        0.095            1
/pif_BigInt/proc/Set               0.019        0.037        0.037            1
/pif_BigInt/New                    0.000        0.037        0.037            1
/pif_BigInt/proc/_GetBlock         0.017        0.022        0.026        18001
/pif_BigInt/proc/_SetBlock         0.014        0.018        0.020        12004
/pif_BigInt/proc/Length            0.008        0.008        0.011        30011
/pif_BigInt/proc/LargestBit        0.000        0.000        0.000            1
/pif_BigInt/proc/Expand            0.000        0.000        0.000            2
/pif_BigInt/proc/Contract          0.000        0.000        0.000            2
/pif_BigInt/proc/Sign              0.000        0.000        0.000            2

I was surprised to see that subtraction was about 21% faster than addition, considering they use almost exactly the same algorithm with only a few minor modifications. I re-ran the addition test with some different sets of numbers, to make sure I wasn't accidentally getting 'nice' values somehow, and I'm seeing speeds similar to the subtraction test now.

                         Profile results (total time)
Proc Name                       Self CPU    Total CPU    Real Time        Calls
---------------------------    ---------    ---------    ---------    ---------
/mob/verb/Add_Test2                0.000        0.090        0.090            1
/pif_BigInt/proc/Add               0.034        0.090        0.090            1
/pif_BigInt/proc/Set               0.014        0.033        0.033            1
/pif_BigInt/New                    0.000        0.033        0.033            1
/pif_BigInt/proc/_SetBlock         0.023        0.027        0.025        12002
/pif_BigInt/proc/_GetBlock         0.010        0.016        0.025        18001
/pif_BigInt/proc/Length            0.009        0.009        0.011        30008
/pif_BigInt/proc/LargestBit        0.000        0.000        0.000            1
/pif_BigInt/proc/Expand            0.000        0.000        0.000            1
/pif_BigInt/proc/Sign              0.000        0.000        0.000            2

I had made a few changes to the addition algorithm, as I found a couple things that were not needed, but none that I thought would speed it up that significantly. Kinda surprising.

[Edit]
Realized I undercounted the number of digits.

Nov 19 2015, 2:05 pm
Popisfizzy	To give an example of the size of the numbers this is processing, here are two randomly generated integers with 24,000 hexadecimal digits, their sum, and their differences.

Nov 19 2015, 2:09 pm
Somepotato	have fun implementing division

Nov 19 2015, 2:13 pm

In response to Somepotato

Popisfizzy

Somepotato wrote:

have fun implementing division

Yeah, that's the shitty part. For addition/subtraction, and multiplication I'm trying to maximize the number of times I use built-in operations, which is the reason why this is working as fast as it is. Division is not as nicely-behaved as either of those, though, which means I won't really be able to use the built-in division operator.

I put it an request for The Art of Computer Programming, vol. 2 from my campus library for an algorithm in there that's supposed to be fairly efficient.

Nov 19 2015, 3:20 pm In response to Popisfizzy
Rushnut	Popisfizzy wrote: To give an example of the size of the numbers this is processing, here are two randomly generated integers with 24,000 hexadecimal digits, their sum, and their differences. Bigint more like fucking massive int

Nov 19 2015, 3:20 pm In response to Rushnut
Konlet	kek

Nov 19 2015, 3:56 pm

In response to Rushnut

Popisfizzy

Rushnut wrote:

Bigint more like fucking massive int

Yeah, and larger than I really expect this library to be used for. Addition and subtraction are fast because they are approximately asymptotically linear in terms of the larger number being added (i.e., if you add a number with n bits to a number m bits, addition will be a function of max(m,n) as m, n -> infinity). That's not too much of a problem.

Multiplication and division are the trickier one. My current algorithm is (I believe) asymptotically n² (more specifically, I believe that it's running time is O(mn)), so it would be slower than some available algorithms for very, very large m, n. If I really expected it to be used regularly for such large numbers, I would implement something like the Schönhage-Strassen algorithm, but algorithms like that are very, very complicated to implement and I would have to study it for a long time to get it. In practice, I don't expect it to be used really for more than a few hundred hexadecimal digits, and I expect it'll mostly be me doing that rather than others.

Nov 19 2015, 3:58 pm
Somepotato	If you need a break from that you could have a go at implementing bigdecimals.

Nov 19 2015, 4:41 pm (Edited on Nov 19 2015, 5:02 pm)

In response to Somepotato

Popisfizzy

I do plan on writing a BigFloat library at some point when I'm done with this BigInt library, using what I've learned from it. The problem is, I need that knowledge for something like a BigFloat library given the way my implementation works. Basically, it has a tradeoff of faster speed of operations, but with a loss of speed for conversion to decimal representation (and more generally, for any representation that can't be represented as an integer power of 2), which is why I've generally been representing values in hexadecimal instead of binary. I've only been able to display decimal values by having Mathematica handle the change-of-base.

What it comes down to is that in order to convert it to decimal, I'll have to use division with remainder repeatedly, which will require a reasonably-efficient division-with-remainder algorithm. The division algorithm is gonna be the one that is most difficult to implement efficiently.

Nov 19 2015, 5:22 pm In response to Popisfizzy
Rushnut	Popisfizzy wrote: asymptotically Don't talk dirty like that, there are kids around.

Nov 19 2015, 5:41 pm
Kozuma3	Created another scripting language this afternoon lel.

Nov 19 2015, 6:16 pm
Byonamous	little pic from my project thought id share

Nov 19 2015, 7:06 pm In response to Byonamous
ManaSoul	How are your animations for this looking :o? It looks good

Nov 19 2015, 7:34 pm (Edited on Nov 19 2015, 7:41 pm) In response to ManaSoul
Byonamous	All advanced animations and stances about 15 states so far but will be more my game will use 10 diff bases. i use a light shading for a anime feel so that i can move at a decent speed. So far great progress.And got the intro into the game. So we getting there. I kno ur going for advanced animations also i was happy to see some one go with a more ambitious base. 8)

Nov 19 2015, 8:50 pm
Ganite	10??? way to much bro start small. EDIT: I say if anything worry about 3 for now.

Nov 19 2015, 9:13 pm (Edited on Nov 19 2015, 9:20 pm) In response to Byonamous
Byonamous	yea i get that but they aren't that much different than each other there just different based of the weaps they hold and special trait moves so its really the same base 10 times with 2-3 states that fit the class.so its pretty manageable.8) and we are on the same page with 3 the game will start with swordsman mage and archer.

Nov 20 2015, 5:39 am

In response to Byonamous

ManaSoul

Byonamous wrote:

All advanced animations and stances about 15 states so far but will be more my game will use 10 diff bases. i use a light shading for a anime feel so that i can move at a decent speed. So far great progress.And got the intro into the game. So we getting there. I kno ur going for advanced animations also i was happy to see some one go with a more ambitious base. 8)

I'm excited !!! I need to try this ASAP haha if you need help let me know I'm always around for support(: . Yeah lol if only there was a quicker way to do overlays my days of spriting wouldn't feel so long ):. Will the bases be different sizes ?

Nov 20 2015, 8:24 am
Kozuma3	So very useful <3 proc/Eval(_) try{. = eval({"var/data=[_];return data"})} catch(){return "<font color=red>error</font>"}

Nov 20 2015, 8:28 am
BlackProgrammer	Hurry up with that KScript sahn, make it handle type lists too. Ex: string phonebook[10] phonebook[0].at(5)