Back to Questions
1.0k
views3
comments
Compute 2^1000
f#

Is there an easy way to compute 2^1000 using the interactive environment? For example, in most of the functional languages I've played with (e.g. Haskell and Erlang) you can compute with large integers (only restriction is your memory). Here's an example using GHCi (Haskell):

1
2
3
4
5
6

Prelude> 2^1000
10715086071862673209484250490600018105614048117055336074437503883703510511249361
22493198378815695858127594672917553146825187145285692314043598457757469857480393
45677748242309854210746050623711418779541821530464749835819412673987675591655439
46077062914571196477686542167660429831652624386837205668069376
Prelude>

I can't even get F# Interactive to compute 2^3:

1
2
3
4
5
6
7
8

> 2 ** 3;;

2 ** 3;;

^^
stdin(2,0): error: FS0001: Type error in the use of the overloaded operator 'Pow'. The type 'int' does not support any operators named 'Pow'

stopped due to error

O.K., It's not as bad as it seems. If you use, 2.0 ** 3.0 it will work. You can also multiply big numbers:

1
2
3
4
5

> 1234567891234567899999999999I * 998847364647823847574747447I;;

val it : Math.BigInt

= 1233144884638469373985835698997105514025327452425252553I

But what about 2^1000?

Thanks,

Dan

.

Microsoft.FSharp.Math.BigInt.pow works fine but the compiler seems to be looking for Microsoft.FSharp.Math.BigInt.Pow (uppercase 'P').

1
2
3
4

> open Microsoft.FSharp.Math.BigInt;;
> pow 2I 1000I;;
val it : bigint
= 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376I

Regards,
Carl

By on 3/26/2008 1:46 PM ()

Here's one way to do this. First define a function,

1
2
3
4

let rec myPowerOf2 n =
match n with
| 0 -> 1I
| n -> 2I*myPowerOf2(n-1)

then:

1
2
3
4
5
6
7
8
9
10
11
12

> 
val myPowerOf2 : int -> bigint

> myPowerOf2 10;;

val it : bigint = 1024I

> myPowerOf2 1000;;

val it : bigint

= 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376I

I still think there should be an easier way to do this...

By on 3/25/2008 7:56 PM ()

I couldn't find the right incantation to augment BigInt with ( ** ), but if you know that you are only working with BigInt's, you can completely override ( ** ) as follows:

1
2
3
4
5
6
7
8
9

let rec BigPow (a:bigint) (p:bigint) :bigint =
  match p with
    | _ when (p = 0I) -> 1I
    | _ when (p >= 1I) -> a * (BigPow (a) (p - 1I))
    | _ -> failwith "Shouldn't Happen"

let ( ** ) : bigint -> bigint -> bigint = BigPow

2I ** 100I

== output ==>

1

> val it : bigint = 1267650600228229401496703205376

.

By on 3/25/2008 10:06 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper