Premature trigger stop

[Monovertex]

Btw, about the integer limitation: the limit is related to digits or simply to the number's value? If it's to the number's value, does it matters if the number is positive or negative?

a few ppl got it already, Pip, Blue, 1 other i think, but i dont know it yet, I thought I had it, but it ended up not working for me

I really am not sure what to do heh

PipeDream already made 2 solution and going on a third

 

[corvusHaunt]

Pipe is cool

>>positive or negative
JASS uses signed int for it's integer, so I'd say no.

 

[SFilip]

maximum possible integer is 2147483648. its signed so the minimum possible is -2147483648. you could use this to start as a negative and consider 4294967296 (2x2147483648) as your maximum, but that's still not enough.
anyway acehart just gave me an idea, gotta try it out

 

[emjlr3]

right........hmmm....and how do you do that in the fly Ace?

im so lost, I really thought I had it, then it ended up not working

o wells, I suck

 

[martix]

>maximum possible integer is 2147483648
Isn't it ....7? 1 less? If it is as you say, then you've shaken my understanding of numbers.

 

[Luth]

>maximum possible integer is 2147483648
Isn't it ....7? 1 less? If it is as you say, then you've shaken my understanding of numbers.

I think you're right. ... but I'm jetlagged, so dont quote me. Aloha from Maui!

 

[AceHart]

"Off by 1" is an all time classic in programming

 

[martix]

"Off by 1" is an all time classic in programming

Yeah, thats the expression I was looking for, but never found
Btw I've been trying to tell people about this a few times, but they don't seem to pay any attention!

 

[AceHart]

http://www.wc3campaigns.net/showpost.php?p=839801&postcount=129

Part of this thread:http://www.wc3campaigns.net/showthread.php?t=86874






(Of course, my name's misspelled... )

 

[SFilip]

congratulations aceRhart
mind showing us your solution (since the contest is over...at least problem #1)?

 

[emjlr3]

yea I still didnt get it

poo on me

maybe the next thing will actually be something that matters, that may actually need ot be used in a map or something

instead of some obscure WE missing feature

 

[martix]

Ace -
> I guess then, that it's OK if someone would ask me over at THs?
We did have a sorta mini-thread about it.
So we do ask you, how?

 

[AceHart]

Objective:
Write the sum of all numbers from 1 to n, where n is any valid positive integer.
So, Sum(3) = 1 + 2 + 3 = 6, your function is supposed to show "6" on screen.

Sum = 1 + 2 + 3 + ... + (n - 2) + (n - 1) + n

Looks like a formula already. Then again...
Maybe it looks better if we write this the other way around?

Sum = n + (n - 1) + (n - 2) + ... + 3 + 2 + 1

Didn't really help. Or did it?

Well, if we take, for example, the first parts of those two lines: 1 and n.
Or, added together: n + 1.
Yeah...
Second parts: 2 and n - 1, added together: n - 1 + 2 = n + 1.
3 and n - 2? Also adds up to n + 1.

Actually, all of those couples add up to n + 1.
And, since there are n of them, that sum would simply be n * (n + 1).

Unfortunately, every number would have been considered twice, which means the final result
we're actually looking for needs to be divided by 2.

All in all, this leads to the formula:

Sum = (n + 1) * n / 2

Which looks like something we can work with.

Division by 2?
Well, if n is even, n can be divided cleanly by 2, problem solved.
If n is odd, then n + 1 will be even, and the division still works.

Good formula.

The big advantage would be that this formula always takes the same time.
With a loop, it runs longer the bigger n is...

Which also leads to another problem:
Sum(1) = 1
Sum(2) = 3
Sum(3) = 6
Sum(4) = 10
Sum(5) = 15

Those numbers grow rather fast. And, we're supposed to do this for any valid positive integer!
They go up to 2147483647.
Very big number.
And, adding even as little as +1 to it will already overflow our integers.

Which means we need some better way. Where better means able to calculate with larger numbers.

Now, up here, I already posted two simple examples.
Let's take the one with 12x34 one more time.
This time, though, with the "school" method:

          1       2 x
          3       4
-------------------
        4x1     4x2
3x1     3x2
-------------------
3x1 (4x1 + 3x2) 4x2
-------------------
3         10      8

almost ok, 8 is fine. But 10 is too big...

3 + 1      0      8
-------------------
4          0      8

Everything fits, final result: 12x34 = 408.

What's the point of this?
Read on:

The result has three parts: r1, r2 and r3
r1 = 3x1
r2 = 4x1 + 3x2
r3 = 4x2

If r3 is too big, keep the rest and carry the "overflow" over to r2.
If r2 is too big, keep the rest and carry the "overflow" over to r1.

Even more variables, let's say 12 is actually a number made of two parts, a1 (1) and a2 (2),
and 34 is made of the parts b1 (3) and b2 (4).

Well,
r1 = b1 x a1
r2 = b2 x a1 + b1 x a2
r3 = b2 x a2

If r3 is too big, keep the rest and carry the "overflow" over to r2.
If r2 is too big, keep the rest and carry the "overflow" over to r1.

Once done, show, as result: "r1r2r3".

Sounds good. And looks generally usable.

In this example, a1, a2, b1 and b2 have been single digit.
But, of course, the very same also works if those parts are larger, like two digits.
See my example up here.

And, a two digits number times a two digits number may give a four digits result (99x99 = 9801)...

We do get a couple products, and they need to fit into integers.
Half of 10 digits (2147483647 has 10 digits) would be 5.
But, not every 10 digits number fits into an integer (9999999999 for example).
Which means you could try to use 4 digits numbers.
8 digits or less intermediate results, even adding a couple of those, fits nicely.

Which is what I did. The input number n is split into three 4 digits parts.
You can try with less, or even do it single digit, but, larger parts are presumably faster to handle.

Another simple problem would be that you can't add 1 to the biggest possible number.
And, we have n + 1 in the formula.
However, (n + 1) * n can be written as n * n + n.
Since, by the time we start calculating, we have 4 digits parts at most, this must work.

Split the number into three parts.
Multiply that thing with itself, add it one more time, divide the entire thing by 2,
and construct a large string to show.
"Construct" because the final result will have 5 parts (work it out on paper if you want),
but the first ones may be 0,
and we don't want to show something like "000000...0000006", but, simply, "6".

function Sum takes integer n returns nothing
    local integer array a  // will take the three parts of "n"
    local integer array s  // the sum, up to five parts
    local integer i
    local integer j
    local integer c = 10000  // needed often, and I'm too lazy to type it every time
    local string result  // guess

    // split the number at every 10000th to get three 4 digits parts
    set a[2] = n / c
    set a[3] = n - a[2] * c
    set a[1] = a[2] / c
    set a[2] = a[2] - a[1] * c

    // the multiplication by itself
    set s[1] = a[1] * a[1]
    set s[2] = a[1] * a[2] + a[2] * a[1]
    set s[3] = a[1] * a[3] + a[2] * a[2] + a[3] * a[1] + a[1]  // + a[1] (and following) add the number one more time
    set s[4] = a[2] * a[3] + a[3] * a[2] + a[2]
    set s[5] = a[3] * a[3] + a[3]

    // some parts are probably too large to fit into 4 digits, here's the overflow handling
    set i = 5  // from right to left
    loop
        set j = s[i] / c             // divide by 10000
        set s[i] = s[i] - j * c      // keep the rest
        set s[i - 1] = s[i - 1] + j  // add the overflow, if any, to the next higher part
        set i = i - 1
        exitwhen i < 2  // the top value always fits
    endloop

    // the entire things needs to be divided by 2
    set i = 0  // like on paper, start at the left, and work your way to the right
    loop
        set i = i + 1
        exitwhen i > 5
        set j = s[i] - (s[i] / 2) * 2    // the rest of the division by two (either 0 or 1)
        set s[i] = s[i] / 2              // divide by two, and forget any decimals
        set s[i + 1] = s[i + 1] + j * c  // add the previously found rest to the next lower part
    endloop

    // find the first part that isn't 0
    set i = 0
    loop
        set i = i + 1
        exitwhen i == 5  // or, for n = 0, every part will be 0.
        exitwhen s[i] != 0
    endloop
    // turn it into a string
    set result = I2S(s[i])
    // add all other parts, if any, as four digits "numbers"
    loop
        set i = i + 1
        exitwhen i > 5
        set result = result + SubString("0000" + I2S(s[i]),StringLength(I2S(s[i])),100)  // looks sorta evil, but it works
    endloop

    // Done
    call DisplayTextToPlayer(GetLocalPlayer(),0,0,result)
endfunction

50 lines of code, very fast, speed does not depend on n.


Yours,
AceHart

 

[martix]

Lol, now I get the whole task
Until now I wasn't sure what was so difficult in it
Thanks Ace

 

[emjlr3]

yup....

 

[Vexorian]

yea I still didnt get it

poo on me

maybe the next thing will actually be something that matters, that may actually need ot be used in a map or something

instead of some obscure WE missing feature

The codemaker engine's core is big num operations, although the base there is binary. save code systems can get much simpler to make and have a better compression if stuff like this is used.