[Snippet] FastPow

[DrizztDoUrden]

Content:

1. Content
2. Intro
3. Macros
4. API description (example here)
5. Changelog

Intro:

I have seen somewhere request for fast powering library. So I made it as our math teacher said. Here are 2 variants - 2 based and 3 based. I haven't still tested yet, but I'll do it tomorrow. Theoretically 3 based will be fast with HUGE numbers, 2 based with mid numbers and comond multipling with small numbers.

Macros:

library FastPow
//! textmacro FastPowMacroBig takes TYPE, MUL, INIT
  function FastPow2$TYPE$ takes $TYPE$ x, integer y returns $TYPE$
    local $TYPE$ temp = $INIT$
    loop
        exitwhen y <= 0
        if y - (y / 2) * 2 == 1 then
            call temp.$MUL$(x)
        endif
        call temp.$MUL$(temp)
        set y = y / 2
    endloop
    return temp
  endfunction
//! endtextmacro
//! textmacro FastPowMacro2 takes TYPE
  function FastPow2$TYPE$ takes $TYPE$ x, integer y returns $TYPE$
    local $TYPE$ temp = 1
    loop
        exitwhen y <= 0
        if y - (y / 2) * 2 == 1 then
            set temp = temp * x
        endif
        set temp = temp * temp
        set y = y / 2
    endloop
    return temp
  endfunction
//! endtextmacro
//! textmacro FastPowMacro3 takes TYPE
  function FastPow3$TYPE$ takes $TYPE$ x, integer y returns $TYPE$
    local $TYPE$ temp = 1
    loop
        exitwhen y <= 0
        if y - (y / 3) * 3 == 1 then
            set temp = temp * x
        elseif y - (y / 3) * 3 == 2 then
            set temp = temp * x * x
        endif
        set temp = temp * temp
        set y = y / 3
    endloop
    return temp
  endfunction
//! endtextmacro
//! runtextmacro FastPowMacro2("integer")
//! runtextmacro FastPowMacro2("real")
//! runtextmacro FastPowMacro3("integer")
//! runtextmacro FastPowMacro3("real")
 //! runtextmacro FastPowMacroBig("BigInt", "multiplyBig", "BigInt.convertString(\"1\", Base[\"0123456789\"])")
endlibrary

API description:

This lib is divided into 3 parts:

• FastPow2
• FastPow3
• FastPow2 for big integers

They pow basing on 2 or 3. You can make FastPow2integer, FastPow2real or/and FastPow3integer, FastPow3real functions for fast powering with 2 based and 3 based algorithms.
You can easily cange using basment or use both. Here all 4 functions are enabled. If you don't need some of them you have just to remove their runtextmacro lines.
Also you can easily change big numbers support - the one in lib is BigInt by Nestharus. To do it you have to change/add+change this line:

//! runtextmacro FastPowMacroBig("BigInt", "multiplyBig", "BigInt.convertString(\"1\", Base[\"0123456789\"])")

like this:

//! runtextmacro FastPowMacroBig("YourLibraryName", "FunctionMultiplyingBigXBig", "LineInitializingATempBigNumberToBeEqual1")

Example of usage:

local integer int
local real r
local BigInt bi

set int = FastPow2integer(2, 10)
call BJDebugMsg(I2S(int))
set r = FastPow2real(3.5, 10)
call BJDebugMsg(R2S(r))
set int = FastPow3integer(2, 10)
call BJDebugMsg(I2S(int))
set r = FastPow3real(3.5, 10)
call BJDebugMsg(R2S(r))
set bi = FastPow3BigInt(5, 70)
call BJDebugMsg(bi.toString())

Example with Nestharus BigInt

Changelog:

2.0

Added 2 based big integers

1.1

Added 3 basement

1.0

First version

 

[Magtheridon96]

Honestly, this is faster than pow(double x, double exp) in C++, but in Jass, this may be slower
(Yeah, Jass is a d*** that way)

 

[DrizztDoUrden]

With big numbers (I'll make it working with some big int libs) it will be much faster. E.G. How long will it take pow to compute 2^1024? 1024 fast cicles. FastPow will do it in 10 3-4 times longer cicles. Or am I wrong? I am using it for RSA cripting
P.S.: K. Stoped using RSA - it made codes ugly and long... Anyway it (big number working) is here now.

 

[Bribe]

With all the interpreting going on behind the scenes with JASS and the hidden operations involved with otherwise simple stuff, I'm almost convinced that one or two iterations through your loop would be slower than a single "Pow" call.

If you want to argue speed, I am going to need you to provide reliable benchmarks. Speed is a tired argument and I have had to deal with such arguments more than any man ever should thanks to Nestharus.

However, if you and Nestharus want to discuss integrating FastPow into his BigInt library, that is an option. However, Nestharus I'm sure would argue that your current approach can crash the thread etc/etc/etc.

 

[Magtheridon96]

Nestharus quit modding.

He's only around here to update his resources (He needs to fix a few bugs here and there.)

 

[Troll-Brain]

Yeah, there is no way that you would beat a jass native function with a custom not native one, especially a math one.
Just remember that jass is before all slowly interpreted.
One day i've even tried to use a real global array read instead of using Cos and Sin.
The benchmark result was about the same if i inlined the index and was slower if i used small formula with R2I for the index.

The only times you beat a jass native function is when it opens a thread and it fires multiple times (like ForForce) or is very expensive like CreateUnit (recycle unit instead)

 

[DrizztDoUrden]

OK... I just made this as it is usually made in c... If it is slower then pow just forget (and may be graveyard) it.
But anyway I don't remember jass allowing to pow any big integers library. I mean as you see this can be used with almost any big integers library, BigInt was just as example - it is first one I found.

 

[Magtheridon96]

Then you should call this BigIntPow and only include that function.
It could be useful.

And if you don't want to crash the thread, then use trigger evaluations based on the number of digits in the BigInt and the magnitude of the exponent.

 

[DrizztDoUrden]

trigger evaluations

What do you mean? I am sorry if answer is obvious - I am sick at the moment

 

[Magtheridon96]

Because of the op limit, we sometimes resort to things like TriggerEvaluate so we can reset the operation count and /not/ crash the thread.

You can do some of the loops, and after a while, you would save the current value you reached in a global and call TriggerEvaluate using a trigger with a fast pow function added to it (using TriggerAddCondition on map init).

You should test how many iterations it takes to hit the op limit with average sized numbers. (Something like 50 digits)

 

[DrizztDoUrden]

Ok, I'll do it when I'll be fine. What do you think about fast hyperoperator function? I mean I am thinking to make it or not, but it won't be really usefull I think.

 

[Bribe]

ForForce and TriggerEvaluate operate at the same speed, so if you are multi-threading just for the sake of multi-threading it makes more sense to use ForForce and avoid needing all the complexity of triggers and conditions.

 

[Magtheridon96]

I guess so.
That way, you can use bj_PLAYER_FORCE[0] and omit your onInit function

 

[Bribe]

I will go ahead and graveyard this unless some benchmarks with real-world numbers can prove that this is faster.