Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Challenges

Print the modular multiplicative inverse / virtual fractions

+2
−1

Goal

Print the modular multiplicative inverse with a modulus of 65536 (or a higher exponent of 2) for odd numbers 1-97.

Example output

Print these values (or an extension of them):

1
43691
52429
28087
36409
35747
20165
61167
61681
51739
53053
14247
23593
55827
49717
31711
33761
44939
7085
28567
39961
48771
20389
18127
22737
64251
21021
46471
60937
55539
38677
61375
4033
19563
4749
43383
61945
51555
14469
5807
18609
17371
64765
60263
18409
12243
54261
23455
41889

Rules

  • Use a modulus of at least $65536 = 2^{16}$. But you can use any modulus $ M = 2^N$ for $N ≥ 16$ and $N \in \mathbb{N} $ .
  • Print the modular multiplicative inverse for at least all the natural, odd values $<98$.
  • You can print it in any normal base.
  • You can print additional stuff, but it should be clear which parts belong to the modular multiplicative inverse and which do not.
  • Your program should print the required output in less than 1 hour on a modern PC (or other hardware that is affordable).

Ungolfed example

#!/usr/bin/env python3

# Calculates the modular multiplicative inverse
def imod(a, n):
  c=1
  while c % a:
    c+=n
  return c//a

# Print the multiplicative inverse for 16-bit integers
n=2**16
for i in range(1,98,2): #For the values 1/1, 1/3, ... 1/97
  b = imod(i,n)
  print("{:>2} * 0x{:>04X} = {:2>} mod 0x{:>04X}".format(i,b,i*b%n,n))


Why these numbers are interesting

You don't have to understand this part in order to participate in the challenge.

There are multiple ways to look at these numbers. All lead to the same numbers. I call them virtual fractions (made up term). Virtual fractions are integers that have the feature that you can multiply them with the denominator and you get the numerator when you store them in a N-Bit integer. This only works for odd denominators. You can even add and multiply virtual fractions and they behave like you would expect from real fractions (assuming you use enough bits).

Example for 1/3

For example, you have the 16 bit unsigned integer with the value 0xAAAB (43691). You can multiply it with 3 and get 1.

  3 * 0xAAAB  =  3 * 0b1010 1010 1010 1011  =  3 * 43691
  =  0x20001  =   0b10 0000 0000 0000 0001  =     131073
Storing it in a 16 bit variable drops the 1 at bit 17:
  =   0x0001  =      0b0000 0000 0000 0001  =          1

This does the following operation: $1 ≡ 3 \cdot 43691 \mod 65536$ (which would be 1%65536 == 43691%65536 or 1&0xFFFF == 43691&0xFFFF in C). This is interesting because that is what a 16-Bit ALU would do when it multiples 0xAAABu * 3u. Therefore, 0xAAAB is like $1/3$.

There are other ways to look at these numbers, but that should be enough for this challenge.

History
Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

1 comment thread

Way too confusing (9 comments)

0 answers

Sign up to answer this question »