bugMIT/GNU Scheme - Bugs: bug #18328, modint:expt doesn't work

 
 

bug #18328: modint:expt doesn't work

Submitted by:  None
Submitted on:  Sun 19 Nov 2006 07:48:07 PM UTC  
 
Category: scmutilsSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Incorrect behavior
Status: NonePrivacy: Public
Assigned to: NoneOriginator Name: Dan Gildea
Originator Email: -unavailable-Open/Closed: Closed
Keywords: 

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Sat 07 Mar 2009 09:06:13 PM UTC, comment #2:

This appears to have been fixed shortly after it was submitted.

Taylor R. Campbell <riastradh>
Project Member
Sun 19 Nov 2006 09:49:54 PM UTC, comment #1:

This is a bug in scmutils, which isn't really a part of the MIT/GNU Scheme system; it's an add-on library maintained by Gerry Sussman. I'll forward the bug report to him, but in the future you should contact him directly: user "gjs", host "csail.mit.edu".

Chris Hanson <cph>
Project Administrator
Sun 19 Nov 2006 07:48:07 PM UTC, original submission:

The expt operator doesn't work for modular integers.

1 ]=> (expt (mod:make 3 10) (mod:make 7 10))

;The procedure #[compiled-closure 12 ("modarith" #x9) #x60 #x1de6008 #x1de683c] has been called with 3 arguments; it requires exactly (2 . 2)
;To continue, call RESTART with an option number:
; (RESTART 1) => Return to read-eval-print level 1.

I think this should fix the problem:

(define (modint:expt base exponent p)
(define (square x)
- (mod:* x x p))
+ (modint:* x x p))
(let lp ((exponent exponent))
(cond ((int:= exponent 0) 1)
((even? exponent)
(square (lp (quotient exponent 2))))
(else
- (mod:* base (lp (int:- exponent 1)) p)))))
+ (modint:* base (lp (int:- exponent 1)) p)))))

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by riastradh (Posted a comment)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 3 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sat 07 Mar 2009 09:06:13 PM UTCriastradhOpen/ClosedOpen=>Closed
    Sun 19 Nov 2006 09:49:54 PM UTCcphCategoryruntime=>scmutils
    Sun 19 Nov 2006 07:48:07 PM UTCNoneCarbon-Copy-=>Added -unavailable-

    Back to the top


    Powered by Savane 3.1-cleanup1