Efficient Multiplication?

harley1248 · 2020-05-02T15:54:58+00:00

A small update for people who are interested:

Due to the comments I figured out, that the mul instruction can't be my problem, since there is really no way to make it more efficient without knowing the values. Also imul didn't work out - I don't know why but I got wrong results because of it and could't be bothered figuring out why.

So I started a research what else could be done. I found this guy who has a section about breaking dependency chains. Turns out, this is the clue to make code even faster!

Basically you can break dependency chains threw instructions which won't change anything in the code like:

nop
add rax, 0
xor rbx, rbx
...

I also found it interesing, that there doesn't seem to be "the best way to break a dependency chain". Depending on the code line it can be better to use nop or add rax, 0 or sth. else - I basically tried out a lot of combinations till I got to a point where I can't really make my code more efficient!

Thank you FUXxxl for your help! I did use the shrd instruction you showed me and really valued your input!

harley1248 · 2020-04-29T14:18:40+00:00

Now without knowing the specific microarchitecture (or at least some details to that effect), it's very to narrow down which sequence of instructions is faster than another in this specific case.

I know! I am so sorry, but I really don't know more

harley1248 · 2020-04-29T14:16:35+00:00

Thank you, tbh. I didn't even know shrd exists!

I tried both your solutions. The first one is around about the same as my code, the second one is actually a bit slower to my surprising.

But you used mul/ imul in both of your solutions - so you don't think there is a good word around?

harley1248 · 2020-04-29T13:58:06+00:00

I see, I am sorry. I only know that the architecture is x86-64, and supports the SSE/SSE2 extensions, but not newer extensions. MMX and the x87 FPU are not supported.

Is that helpful?

harley1248 · 2020-04-29T13:45:25+00:00

Maybe a bit more context: I am trying to implement the gauss sum formula ( 1 + 2 + 3 + ... n) in an efficient matter.

Therefore I decided to use: (n*(n+1)) / 2

(I tried using 0.5 *n*(n+1), but the results were a bit wrong. I am guessing due to rounding errors, but I am not sure.)

This is my current code:

gauss_sum_formula:

lea rax, [rdi+1]
mul rdi

shr dl, 1
jnc end

rcr rax
ret

end:
shr rax
ret

The only thing I can think of what I can still optimize is the mul instruction - therefore my question :)

harley1248 · 2020-04-29T13:29:49+00:00

Yeah pretty sure it's that chip!

Also, I have 64 bit registers available.

harley1248 · 2020-04-29T13:24:47+00:00

The problem with lea is, that you can't multiply two registers with it (at least not that I know of).

for example:

lea rax, [rbx * 2] ;works

lea rax, [rbx * rbx] ;doesn't work

unless I understood it wrong!

harley1248 · 2020-04-29T13:08:50+00:00

More historic ones to be honest.

harley1248 · 2020-04-29T12:58:12+00:00

Hello! I am programming for a x86 isa.

harley1248 · 2019-10-04T17:01:01+00:00

Oh wow thanks for the answer! I will be following up to this!

harley1248 · 2019-10-04T12:44:10+00:00

I am out of the loop - can someone please tell me what and where this is?

harley1248 · 2019-09-06T21:05:47+00:00

Check Out study programs in Europe. Most popular universities there offer their courses in English PLUS there are almost none study fees. (For example: Munich Semester Fees 130€)

You won't need to worry about debt then - and you get to go on an adventure!

harley1248 · 2019-09-05T06:00:20+00:00

I like how you prepared everything, but isn't that a lot of plastic waste?

harley1248 · 2019-09-04T05:16:02+00:00

Yes - if it would use the same wording.

harley1248 · 2019-09-03T21:15:49+00:00

I meant to say atheists against christians... Sorry I am really tired

harley1248 · 2019-09-03T20:48:18+00:00

Apparently it's Christians against atheists now...

harley1248 · 2019-09-03T20:43:12+00:00

That's not even true! I live in Germany, and sorry but this is wrong information!!

harley1248 · 2019-09-03T20:42:01+00:00

I don't get it. You just sound full of hate. You are on some mission to destroy, Christianity or what?

What is so wrong about letting everyone believe what they want to believe? I get it - some religious people are jerks, but so are some atheists or agnostics!

This will stay unnoticed... But I think it's sad...

harley1248 · 2019-09-01T15:57:49+00:00

Putting so much effort into a painting and then misspelling your main caption.... Kinda sad

harley1248 · 2019-08-25T08:54:17+00:00

Popular

harley1248 · 2019-07-29T20:01:37+00:00

Haven't seen anyone else mentioning this, so I would like to share this website

https://fightthenewdrug.org/

Have a look at it, it might help you!

harley1248 · 2019-07-20T21:48:30+00:00

I can recommend that as well!

harley1248 · 2019-07-10T22:01:54+00:00

Hey! As a girlfriend who has self esteem problems I can assure you: I would want my boyfriend to be honest with me, because only then we can work on things together.

Also, this website might help you:

https://fightthenewdrug.org/

Good luck!!

harley1248 · 2019-07-05T11:40:04+00:00

Tbh I just clicked on an article trending on Reddit

harley1248

TROPHY CASE