Scientific Calculations on EVM

Transcript

Hello. All right, guys. Thank you for showing up. I really appreciate it. Um, show of hands. How many of you enjoy recreational math? Okay, applaud everybody else because we're going to do some of that today. Um, this is scientific calculations on EVM or huffing gas for 38 decimals of precision. Um, I made some nice animations and you will not see them today um because my computer is not working right. Um the main point today is how to perform calculations without leaving the blockchain and um without being satisfied with 18 decimals of precision which is normal.

Um everybody know what WOD math is? No, you do. Yeah. Okay, good. Um so we'll talk a little bit about that. Um let's just get right into it. What are scientific calculations? Um what I mean by this is generally transcendental functions like the exp. That's my favorite. Natural log square root of x. And then of course powers. And this last one, anybody know what this is? Lambert w. It's a special one that cannot be represented with primitive functions. So, um, yeah, for scientific calculations, we also need them decimal and signed. Um, so your regular u int 128 is not really good enough for these curves. and they must be thoroughly

tested with consistent precision so that there's no spaces in the domain where numbers come out all wrong. Uh why do we need high precision? Yeah, we can't leave dust in a contract because it won't close and if the rounding isn't right in the other direction, the call will revert and nothing will happen. Um another great reason is that smart smart contracts are actually pretty dumb. uh they do not have the ability to use bell curves or calculate the area under a curve for example generally speaking something you can't do in solidity. There are some other math libraries that we'll talk about but um I don't really think they're sufficient either. Your other option is to go to an oracle. Um you know you can go to chain link for random

numbers. I don't have a good way of making random numbers on chain obviously. Um these are expensive and they're vulnerable. It's the number one place to get hacked by having injections of bad information. So, what data primitives do we have available? Well, Viper's got decimals, but they're locked at fixed point with 10 decimals of precision. So, when you start doing these curves, you wind up ultimately with like six places of precision, which is totally not enough for smart contracts unless you're just doing zcores. Uh, Solidity has Uint 128, int 128, all these others, but everything's really just Uint 20 or 256.

It's just a 256-bit word actually. Technically, it's not really even a number. So, good luck. Have fun. Uh, you are highly incentivized to make your own primitives. So, I know that there's other ways of targeting the EVM, but these are the main ones that I know about. Um, everybody's heard of Solidity. Um, this is JS like. Uh, I don't know why you would do that to a language. Um, it's considered, you know, very high level. It's very capable. The bite codes are pretty large. Uh so this is really bad for doing math. You can use ule which is an assembler language that inlines in solidity or you can stand by itself. Uh many people are quite happy with this.

It seems really powerful. I've never used it. Uh when I started making math contracts about four years ago, I used Viper because of the built-in decimal system. Uh it doesn't offer decimal exponents. So I had to move on to Huff. Uh, Huff is my favorite because it's it's got a a one toone relationship between the op codes and the bite code. The bite code is really really small and in many cases the gas fees are determinant. So this is really good for an intermediary contract that that just functions as a calculator.

So let's talk about wadm. Wadmath is essentially multiplying everything by one quintilion. I you know there's not really a way around this um when you're talking about bit shifters and the EVM is a binary system so you kind of have to do it. Um lots of uh exchanges use the ray which is 10 to the 27th and uh others internally calculate to 10 to the 45th and then outwardly they use a wad or array so that they're compatible with other things.

Uh so yeah if you want to represent this calculation 0.5 * 3.0 0 equ= 1.5. This is actually what you have to do. 5 * 10 17th * 3 * 10 18th all divided 10 18th. It's it's it's a roundabout way, right? Um sorry, but ultimately you have to you scale up and you calculate and then you scale back down. So uh this guy John Napier, he's a Scottish sorcerer from 1600s. He kind of invented logarithms by accident.

and he really liked wad math. Um he did not enjoy uh long division and so he avoided doing long division by multiplying everything by 10 million. So this is exactly the same trick 400 years ago. And uh so yeah the whole purpose of what he's doing here he imagined one dot moving at a linear speed towards some finish line and another dot um moving at a geometric rate related to how much space it has left before the finish line. So you know this one would continue on and this one would eventually get there and now the scale is bigger and you and you have essentially the first logarithms. Um this other mathematician called Briggs took a ship up there next year and said,

"Hey man, uh this would be way better if we recalculated this in base 10, which became known as the common log." And um yeah, Nate Pier said, "I'm very old and I'm not going to do that." So he went home and did it himself and released this tables of magic numbers for the next 10 years or so from 1617 to 1624 which reduced multiplication to addition and division to subtraction. You guys remember this from high school? Yeah. Cool. Yeah, it's it's all the same stuff. Um and we got pretty far on that for a very long time.

So at this point you should be familiar with the scaling trick. it is never going to change but we follow the same playbook as Briggs in precomputing stuff. So in um fix point 127 which is my data primitive that I'm about to explain there's one workhorse algorithm log base 2 because EVM is a binary system this has to be the workhorse algorithm that the others are based off of and if we have this working well enough then these ones can be computed with just multiply shift and add so they become cheaper and considerably more accurate than you would expect.

So what is fixoint.127? It is a smart contract and a data type and it has precomputed tables in it and functions to go with them. Um there is one sign bit and I sacrifice one bit from the integer magnitude. So domain's a bit smaller than it could be perhaps and then 128 bits for the fractional uh part. And we'll go to the full 128 bit fractional depth for all these calculations. So let's talk about the premputation principle a little bit. If you want to do e to the x for example or another transcendental function in school lots of times they will have you calculate it like this with a tailaylor series expansion which is an infinite series

but usually they're just like do 25 and you're okay. Well I don't know if you notice there's there's exponents there's lots of divisions there's factorials not cheap. And in a fixed point system, the rounding errors compound. And by the time you get to maybe the 10th or the 15th um figure, you just have the wrong answer. It's just it's like it's not just a little wrong, it's very very wrong. So don't ever try to use Taylor series expansions on the EVM. It's not going to work. Here's a brief look at what we have for precomputed values. There's natural log of two and its inverse. These are just numbers. And this exists for the bridge

between the natural log and log base 2. And of course, yeah, square root of two and inverse of e are there. I think pi might be in there too, but we don't really need it. It's just fun. Um, just for range reduction. And then of course bunch of precomputed coefficients for miniax polomials and for range reduction techniques. This gives a similar effect to the Taylor series expansion when it goes well and it's considerably cheaper, but it's it's very hard to compute these um for me. So, okay, where what's the leaderboard look like? Um, Solidity is the king right now of math libraries.

Have you guys ever heard of any of these? And none of this looks familiar. This man >> is you think King is PRB? Did you make PRB? Okay, I got scared for a moment. >> Very cool. Well, it's very nice. I'm like I'm very happy with this one, especially because the domain is actually so large. Um, these three all exist within the space of 128 so that when you multiply numbers, you don't slam against the ceiling of of the um 256-bit word. But we have a different multiplication algorithm, so it's it's actually not a problem. Uh, yeah.

Anyway, uh any questions about this? This all makes sense? Okay, great. So, gas versus precision. Um this graph is a little bit strange because fix point 127 which is over here. Let's see. Oh, I got a laser me. Um this contains the cost of static calls because it is a contract and not like a pure math library. Um, this is the result of 41,000 different fuzz tests across all the functions that are available for all of these libraries given in the given in the format that they like. So, Solidity is the purple one and it's got really really strong precision. This is exp. So, there's

going to be a range probably near zero where um where the calculations don't really work out that well. The way that we got this um precision in terms of digits is this is compared against an oracle that is correct to a 100 uh digits of precision and we just count up however many digits are exactly the same. So yeah, at the expense of a bit more gas we don't have any variation in the precision and um that's because we iterate and the other ones don't really iterate.

So yeah, um PRB math I agree it's really fantastic. It's very very cool. But I also only learned about it after I started this project. So uh yeah, do it that what you will try to do some more research next time I guess. Um so why is a solid standard? It's optimized uh gas for WADM math. Um most of the math is safe within the WAD scale. They're really really good at that. And uh they have Lambert W, the crown jewel. So this is the special function I mentioned earlier that cannot be represented with primitives and um it's useful to exchanges for calculating the depth of liquidity pools or derivative prices based on assets of other regular um real assets

and people got really excited about that. But our design philosophy with fixed point 127 is ideally everything should be defined by primitive functions but in practice we're going to have one workhorse algorithm for your hardware. which is log base 2 and um we must exhibit terminal precision like we said. So some of you may remember IBM system 360 a long time ago it established the 8bit bite. Prior to that it was common to have sets of vacuum tubes in three bit bytes which is really weird. Um so yeah they kind of established the dominance of hexadimal and the ease of changing between you know log base 2 and hex. So the the same things across 400

years, we're doing the same thing over and over. So what are the elements of a good math contract? I think they should be defined peace-wise and procedurally. You cannot have loops. Things can't loop. Um you should start with a bit hack or a lookup table. Anybody know about CarMax fast reverse? This uh Quake 3 algorithm. It's very famous. It's a really really fun algorithm. You should check it out. um it's just one single procedure and it and it produces like the inverse square uh very quickly. So this is how this was a revolution in rate tracing I guess. Um [clears throat] so anyway after you get through the bit hack or the lookup table you should use a polomial with precomputed coefficients and then you might want to do fast convergence

iterations and then you may want to avoid catastrophic cancellation which is when two numbers are very very close together and you divide them you get errors only or if things are very very close to zero fix point doesn't handle them well. So you need a special algorithm to finish off and if you want to extend the range beyond that you might use an asmtotic convergent iteration which I did not choose to use. So how does our 256x 256 bit multiply works? Um we cut the number into two pieces and uh you know a high and a low part. These are using extra small numbers 12,345 and 67,890.

So it's easy to see what's going on. We're going to use a scale of a thousand. You cut them into pieces. You multiply them together. You reintroduce the scale and then you sum them up. [clears throat] And that's the answer. You can check it. And this is what it looks like in Huff. This is at least this is the first part. Um, so any of you who have not read or used Huff before, it's it's just an assembler language. It's really fun. It's it's very efficient and Claude is not very good at it yet. So okay let's talk about log base 2 of x the most important algorithm for us um say you want to find log base 2 of toao uh toao is the new pi it's just 2 pi and

so we find the most significant bit which in this case is six right six is the first bit the biggest chunk and because it lies between 2 ^2 and 2 cubed the integer part in our in our binary system is two from there we begin a range reduction. So going down with fractional powers of two depending on whether the boundary is before or after uh the value that you've got um you can just you can add it on here and uh and we do this seven times. I'm sorry I had I had really cool animations but they're not showing today. Um yeah so anyway you get through the range reduction and then there's the polomial

technique and this is a 13 degree polomial. So the first through fifth degrees get you closer, but by the time you get to 13, we've actually closed out all 128 bits. So this works pretty good. And we've reduced log two to to essentially just bit shifting. [clears throat] And um yeah, there's not much more to say about that. So once you get to natural log of x, congratulations. It's just a wrapper because we've got natural log of two premputed in the system. you compute log base 2 of x multiply by this and you've now just changed bases. It is just this very very very nice.

So um yeah we start with uh all right square root. Yeah let's talk about the karmmat bit hack approach. So for this one we we start by finding the most significant bit. Um say we want to find um the square root of e or e squ that's what I put in here. Um the first significant bit is two and we have to shift it so that it falls in the right place within uh our 256- bit word. So most significant bit in this case is actually 130 and if [clears throat] it's odd then we have to adjust for that by this premputed value of two. But when you get through this um this first bit of the procedure you should have about one bit. You should be around like 2

point 2 2.7 or 2.8 something like that. And then we use Newton iterations. So this is what a Newton iteration looks like. Your next term is just this. And each time that you iterate, you double the digits of precision. So this is quadratic convergence. Got you. I'm really close to the end. Thank you. Um yeah, quadratic convergence. There's also a cubic convergent algorithm made by the comet guy. And there's a um a fourth order cortic convergence um which actually is too expensive to use for this. In this case, you only want quadratic because these um these are such cheap iterations. So anyway, by the time you get through seven of these, that's the

end. You've got your answer. And it looks like this in huff. Give you a little second to stare at it. So the interesting part is see there's no loop. It's all completely procedural. So x to the y. Let's talk about how to do powers. Once you've got two to the x and you've got log two of x, well, that's kind of it. Actually, you don't really need to do anything else. Why are other libraries just integer only?

I I'm I'm still don't understand this. Like Viper gives you you can do a decimal base, but only an integer power. And I think ABDK math only gives you integer bases and powers. Um, what about PRB math? Do you know? >> Really? >> Yeah, they do the same thing. Yeah. Yeah. Yeah. Of course, the same thing. Uh, okay. Well, interesting. Um, anyway, on to Lambert W. This is the final algorithm that I want to talk to you about. Um, this is a hard one. uh because yeah like I said it can't be can't be expressed as elementaryaries for this one we start with a lookup table so this is a curve that roughly matches

this function and we've got a known domain so there's it actually does go a little bit negative there's more here two minutes got you um but then following that we use a fast uh convergent iteration this is the Fischer Schaefer Cwley iteration it was written in 1973 um based on the householder method from 1970 is this is a cortic uh convergence. So it just converges extremely fast. Um but by the time you get to the end you have catastrophic cancellation issues. So you need to use another convergence called the yakono void and um by the time you get through that you've reached 128 bit depth again.

So click through and by the time you get to the end, the tangent line is pretty much straight up and down. It's there's obviously going to be some variation in any fixed point system, but um but it works. Anyway, that's the end of my talk. Thank you very much. You can check all this out on blocker.com. Um it is on a test net. Don't worry, you won't lose your tokens. There's some games to play. Please make a badge and stuff. And um my company is called Secure Data Research. So if you're interested in any of this or how I may help you improve your mathematics, please get in touch with me after the show. Thank you very much. All right.

[applause] Questions? >> Sir, my voice to the right level. All right. Um yeah the hard question floating point all of this is great and now we go to plus synth minus in and nonstandards >> I'm working on floating point right now actually um the subnormals are the hard part >> subnormals and sort of undefined values what is your view on how to handle them because that's ultimately what a lot of there's a lot of bugs associated to different choices there and there's also a lot of inefficiencies >> well the ILE E754 which defined

floatingoint standard in 1985 um is is just something that is widely accepted. Right? So there's there's certain rounding rules that everyone adheres to and as such the system is determinate. It works the same for everybody and that's as good as you're going to get basically. Uh there's there's no substitute for pencil and paper. >> So you are going to adhere to those specifications. That that's your plan. >> I'm working on it. It's still buggy. All right. Yeah. Exactly. But thank you. Great question. >> Yeah. Thank you. Hi there. In your uh library comparison, I didn't see Snackmate, the math library there. It's a Viper module.

>> Oh, really? >> Yeah. And there is lots of bit shifting and premputee and log to magic. >> You should have a look at this. >> Okay. Let me talk to you after after uh Yeah, I understand there's a there's a ton of people trying to do the same thing. Um but um I wanted to do it on my own. Yeah. Anybody else? Okay, thank you very much guys. You did great.