Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

As a part of programming an Elliptic Curve Method with montgomery coordinates in Magma, I need to have an algorithm to convert a number from decimal notation to binary notation. Since there is no inbuilt function for this (as far as I know?), I made one myself. However, for the numbers I'm trying to decompose, the binary representation algorithm takes up 90% of the execution time (which is horrible).

Current algorithm is:

binarydigits := function(n)
m:=Floor(Log(2,n));
digits:=[];
while m ge 0 do
k:=n div 2^m;
digits:=Append(digits,k);
n:=n-k*2^m;
m:=m-1;
end while;
return digits;
end function;

Any suggestions to improve this? All I could think of was storing 2^m and calculating 2^(m-1) from that, etc...

share|improve this question

1 Answer 1

up vote 1 down vote accepted

You could use the implemented function Intseq.

It takes two arguments, first the integer you want to expand, second the base, and returns the expansion in a list. So for example, the base 2 representation of $10$ is $1010$ and

Intseq(10,2)

returns

[ 0, 1, 0, 1 ]

The coefficient of the highest power of $2$ is the rightmost one. You can use

Reverse(Intseq(10,2))

to reverse the order and get $[ 1, 0, 1, 0]$.

share|improve this answer
    
Please let me know if you try this and it's actually faster. –  Gregor Bruns Nov 17 '12 at 1:30
1  
I've just started testing this, and for a p with 43452 digits, the old algorith took about 90 seconds, yours took less than one, it's probably safe to say this is a LOT better. Thanks! –  user49719 Nov 17 '12 at 11:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.