All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
NegaTernary Nuance (Posted on 2016-09-14) Difficulty: 3 of 5
Devise an algorithm for writing any positive base ten rational number in negaternary system.

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 1 of 3
For rational numbers, the numerator and denominator can be treated separately as integers.

This required only a slight variation of the base function I had been using, adding the line

    If d < 0 Then d = d - b: q = q + 1
    
shown below.

Also, to catch attempts at converting negative numbers in an ordinary positive base, I added

  If n < 0 And b > 0 Then base$ = "-----": Exit Function
  
but that's not essential to the negaternary algorithm.

Of course for negaternary, the base, b, will need to be -3.


Function base$(n, b)
  If n < 0 And b > 0 Then base$ = "-----": Exit Function
  v$ = ""
  n2 = n
  Do
    q = Int(n2 / b)
    d = n2 - q * b
    If d < 0 Then d = d - b: q = q + 1
    n2 = q
    v$ = Mid("0123456789abcdefghijklmnopqrstuvwxyz", d + 1, 1) + v$
  Loop Until n2 = 0
  base$ = v$
End Function

The function is called by the following driver for the integers -10 to 10, first for base +3, then for base -3:

DefDbl A-Z
Dim crlf$


Private Sub Form_Load()
 Form1.Visible = True
 
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
 For i = -10 To 10
   Text1.Text = Text1.Text & base$(i, 3) & crlf
 Next
 Text1.Text = Text1.Text & crlf
 For i = -10 To 10
   Text1.Text = Text1.Text & base$(i, -3) & crlf
 Next
 
 Text1.Text = Text1.Text & crlf & " done"
  
End Sub

The results are:

-----
-----
-----
-----
-----
-----
-----
-----
-----
-----
0
1
2
10
11
12
20
21
22
100
101

1212
1200
1201
1202
20
21
22
10
11
12
0
1
2
120
121
122
110
111
112
100
101

showing first the rejection of negative number representation in positive base 3, and then a set of values matching those in the linked explanation of negaternary representation.

One could of course change the function take only one parameter, the integer to be converted, and then use -3 wherever b is used.  Following that, one can make a function that takes in two integers (representing numerator and denominator) and apply the base conversion algorithm to each separately.

For negative fractions you presumably have a choice of having a negative numerator or a negative denominator, so that -3/8 could be either 10/112 or 120/1201. 

Indeed the following program produces 10/112 in response to an input of -3/8:

DECLARE FUNCTION base$ (nu#, b#)
DEFDBL A-Z

DO
  INPUT n$
  ix = INSTR(n$, "/")
  IF ix = 0 THEN EXIT DO
  numer = VAL(LEFT$(n$, ix - 1))
  denom = VAL(MID$(n$, ix + 1))
  PRINT base$(numer, -3) + "/" + base$(denom, -3)
LOOP

END

FUNCTION base$ (nu, b)
  IF nu < 0 AND b > 0 THEN base$ = "-----": EXIT FUNCTION
  v$ = ""
  n2 = nu
  DO
    q = INT(n2 / b)
    d = n2 - q * b
    IF d < 0 THEN d = d - b: q = q + 1
    n2 = q
    v$ = MID$("0123456789abcdefghijklmnopqrstuvwxyz", d + 1, 1) + v$
  LOOP UNTIL n2 = 0
  base$ = v$
END FUNCTION


  Posted by Charlie on 2016-09-14 11:01:03
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information