2010/8/29 Levente Uzonyi <leves at elte.hu>:
> On Sat, 28 Aug 2010, Nicolas Cellier wrote:
>
>>
>
> snip
>
> I just took a look at the extension methods (there are quite a lot) and most
> of them can be simplified or removed.
>
>> For example
>> http://lists.squeakfoundation.org/pipermail/squeak-dev/2008-July/130162.html
>
> Like this.
>
>> Maybe http://bugs.squeak.org/view.php?id=7109 would serve a bit too...
>
> Hm. This looks interresting, I guess some optimizations are already
> implemented:
>
> | x |
> x := SmallInteger maxVal raisedTo: 100.
> #(-1600 -1597 1597 1600) collect: [ :shift |
>        [ 1 to: 100000 do: [ :i | x bitShift: shift ] ] timeToRun ].
> "CogVM  ===> #(150 147 271 64)"
> "SquakVM ===> #(97 118 343 71)"
>
>
> Levente
>

I should have a look at source then...

Currently I'm playing with modular arithmetic bottlenecks.
It seems that NINV algorithm (
http://www.iacr.org/archive/ches2005/017.pdf ) is better than binary
one employed for modular inversion.
I get near a 2x factor on this specific method, leading to roughly 15%
improvment on this kind of sequence
		h := hasher hashMessage: 'Nicolas Cellier'.
		sig := dsa computeSignatureForMessageHash: h privateKey: privateKey.
		dsa signatureToString: sig
I'm quite sure there exist a Lehmer's variant to the extended Euclid
used to compute the inverse. I don't own Knuth bible and my brain is
just too tired to reinvent.

Anyway, the biggest contributor is #raisedTo:modulo: and it can be
improved to for sure (I previously failed trying to use Montgomery).

Nicolas


NINVinverseOf: x mod: n
	"NINV algorithm variant"

	| v u u1 v1 f fv t1 b result result2 |
	((x <= 0) or: [n <= 0]) ifTrue: [self error: 'x and n must be greater
than zero'].
	x >= n ifTrue: [self error: 'x must be < n'].

	u := x.
	v := n.
	b := (v highBit + 1).
	f := 1 bitShift: b.
	u1 := (u bitShift: b) + 1.
	v1 := (v bitShift: b).
	fv := f + v.
	[v1 >= fv] whileTrue:
		[t1 := v1.
		v1 := u1 \\ v1.
		u1 := t1].
	result := v1 - f.
	(result2 := result + v) > 0
		ifFalse: [self error: 'no inverse'].
	^result positive
		ifTrue: [result]
		ifFalse: [result2]


>>
>> Nicolas
>>
>>>>
>>>>>
>>>>> The convention is to use hyphenation. As Andreas suggested, that would
>>>>> be
>>>>> "Crypto-Core", "Crypto-Core-Tests" etc.
>>>>
>>>> The problem with that approach is the the Test package gets included
>>>> with
>>>> the core package.  In the example of "Kernel" and "KernelTests"
>>>> hyphenation
>>>> is not used.
>>>>
>>>> Rob
>>>>
>>>>
>>>>
>>>>
>>>
>>>
>>
>
>
>
>