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
add comment

1 Answer 1

up vote 2 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! –  Koeneuze Nov 17 '12 at 11:59
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.