Try to implement n-ary addition in Java

Moe Nishinozono spread her hands next to her face. It is not a gesture that mankind has adopted the decimal system. (From "Thirty Little Indians" in Hiroshi Mori's short story "Erasing Madoromi")

1. 1. Introduction

The other day, I was rereading the above mystery book that I found while organizing the bookshelf of my parents' house, but I came to think that I would like to make a program related to $ n $ notation because it is a big deal. .. So, this time, I will implement quaternary addition in Java as an example of $ n $ notation. As the title says $ n $, we aim for coding that can be used in binary, quaternary, or hexadecimal notation.

2. Problem setting

Suppose there are people in some country who are always calculating in quaternary notation. The numbers they use are different from the numbers we use, and they seem to resemble the alphabet. After investigating, I found that the correspondence was as follows.

If they write "ITPM", it's $ 1203_ {(4)} $ in the decimal number we use, that is

1203_{(4)} = 1 × 4^3 + 2 × 4^2 + 0 × 4 + 3 × 1 = 64 + 32 + 0 + 3 = 99

It means that Given two quaternary numbers, create a program in which the result of adding them is output in quaternary notation using the above alphabet. For example, "I" and "TPM"

1_{(4)} + 203_{(4)} = 1 + 35 = 36 = 210_{(4)}

Therefore, it is assumed that "TIP" is output. As I wrote at the beginning, this time I would like to write not only the quaternary processing but also a little abstractly as $ n $ notation.

3. 3. Implementation

Since it is difficult to create all the calculation processes with $ n $ base numbers, we will convert the two numbers to decimal numbers, calculate them, and then return them to $ n $ base numbers.

NAryNumber class

First, the value of $ n $, which indicates what the base is, and the number or letter used in each digit of the $ n $ base (for example, in hexadecimal, instead of decimal 10, 11, 12, ……, 15). Create a class NAryNumber that stores A, B, C, ……, F). In addition, one alphabet [A-Za-z] or number [0-9] shall be assigned to each place.

class NAryNumber {
	private int N;									//N value of N-ary
	private char[] characters;						// 0～N-Character corresponding to 1
	private HashMap<Character, Integer> numbers;	// 0～N-The number corresponding to the first letter

	public NAryNumber(int n, char[] c) {
		this.N = n;
		this.characters = c.clone();
		this.numbers = new HashMap<Character, Integer>();
		for (int i = 0; i < this.characters.length; i ++) {
			numbers.put(this.characters[i], i);
		}
	}
}

Decimal uses 10 numbers from 0 to 9, but similarly $ n $ uses $ n $ characters from 0 to $ n-1 $. The first member variable N contains the value of this $ n $. The characters assigned to each number are entered in the char type array characters, but the order of entry is always the character corresponding to 0, the character corresponding to 1, the character corresponding to 2, and so on. And each value of 0, 1, 2, …… is stored in a data type called associative array instead of an array named numbers. This associative array is the part of this article that makes me feel good even though I don't understand it well.

Ordinary arrays are always ordered by integers greater than or equal to 0, such as 0th, 1st, and 2nd. At this time, 0, 1, 2, …… are called __index __ or __subscript __. Associative arrays, on the other hand, can use strings as well as integers for indexes. The character string used for the index at this time is called key (key).

The reason why I decided to use an associative array in the first place is that, for example, if you try to convert a quaternary number to a decimal number using the above quaternary system, the char type array characters alone will not be enough. 'T' is here! ⇒ What number is the stored character'T'? ⇒ (While checking the values in the array one by one) Oh, it's the third! ⇒ Then it's 2 This is because I thought it would be a hassle to write a little (although it is not impossible). On the other hand, if you use the associative array numbers, you can make the key'T'attach 2 to it, so you can get 2 just by writing numbers.get ('T').

In the NAryNumber class, create a method convFromNAryToDec that converts a given $ n $ decimal number to a decimal number and a method convFromDecToNAry that converts a given decimal number to a $ n $ decimal number.

convFromNAryToDec method

To convert a $ n $ decimal number to a decimal number, you need to find out what the digit is. For example, in decimal notation, the 1st place is followed by the 10th place, the 100th place, and the 1000th place. In binary notation, the 1st place is followed by the 2nd place, the 4th place, and the 8th place. In this way, in the $ n $ system, the $ n $ place, the $ n ^ 2 $ place, and the $ n ^ 3 $ place are followed in order from the 1st place, so multiply that number by the number of each place. Finally, find the sum of them and you have a $ n $ base. Since the number of digits entered has not been decided, we will calculate the number of digits from the length of the character string. That's why I decided to assign one letter to each person earlier.

public int convFromNAryToDec(String nAry) {
	int dec = 0;	//Value converted from N-ary to decimal
	for (int i = 0; i < nAry.length(); i ++) {
		//Find the sum in order from the 1st place
		dec += numbers.get(nAry.charAt(nAry.length() - 1 - i)) * Math.pow(N, i);
	}
	return dec;
}

convFromDecToNAry method

I'm converting from decimal to $ n $, but this time it's the opposite, that is, dividing instead of multiplying. In the $ n $ system, the next digit increases as the number of $ n $ counts, so we want to know how many $ n $ pieces can be grouped together, that is, how many times they are moved up. However, note that the remainder obtained by dividing by $ n $ is the number of each digit, which is calculated in order from the __1 digit. In other words, if you connect the remainders in the order you asked for them, the answers will be in the reverse order. So, at the end, you need to reverse the order of the strings.

public String convFromDecToNAry(int dec) {
	String nAryRev = "";
	//The order in which the remainder was sought(Reverse order)Convert to N-ary
	while (dec >= this.N) {
		int rem = dec % this.N;
		dec = (dec - rem) / N;
		nAryRev += this.characters[rem];
	}
	nAryRev += this.characters[dec];
	//Invert the string and then return
	return new StringBuffer(nAryRev).reverse().toString();
}

Lastly, I will create the input part, but since it is troublesome to input the value of $ n $ and the characters used for each place from the console every time, I will write the value directly in the program only this time. For the time being, we are planning a sequel, but in that case we will read the settings written in the text file, so please forgive me this time.

4. Complete

As such, the completed program is as follows. In the quaternary setting shown at the beginning, the input part is written to calculate I + TPM. The output result will be TIP.

import java.util.HashMap;

class NAryNumberTest {
	public static void main(String args[]) {
		//input
		int N = 4;
		char[] characters = {'P', 'I', 'T', 'M'};
		String val1 = "I";
		String val2 = "TPM";
		
		//processing
		NAryNumber nary = new NAryNumber(N, characters);
		String result = nary.convFromDecToNAry(
			nary.convFromNAryToDec(val1) + nary.convFromNAryToDec(val2)
		);
		System.out.println(result);
	}
}

class NAryNumber {
	private int N;									//N value of N-ary
	private char[] characters;						// 0～N-Character corresponding to 1
	private HashMap<Character, Integer> numbers;	// 0～N-The number corresponding to the first letter

	public NAryNumber(int n, char[] c) {
		this.N = n;
		this.characters = c.clone();
		this.numbers = new HashMap<Character, Integer>();
		for (int i = 0; i < this.characters.length; i ++) {
			numbers.put(this.characters[i], i);
		}
	}
	public int convFromNAryToDec(String nAry) {
		int dec = 0;	//Value converted from N-ary to decimal
		for (int i = 0; i < nAry.length(); i ++) {
			//Find the sum in order from the 1st place
			dec += numbers.get(nAry.charAt(nAry.length() - 1 - i)) * Math.pow(N, i);
		}
		return dec;
	}
	public String convFromDecToNAry(int dec) {
		String nAryRev = "";
		//The order in which the remainder was sought(Reverse order)Convert to N-ary
		while (dec >= this.N) {
			int rem = dec % this.N;
			dec = (dec - rem) / N;
			nAryRev += this.characters[rem];
		}
		nAryRev += this.characters[dec];
		//Invert the string and then return
		return new StringBuffer(nAryRev).reverse().toString();
	}
}

By the way, if you rewrite the input part at the beginning as follows, you can also calculate in hexadecimal notation. The output result will be FFFFF.

import java.util.HashMap;

class NAryNumberTest {
	public static void main(String args[]) {
		//input
		int N = 16;
		char[] characters = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
				'A', 'B', 'C', 'D', 'E', 'F'};
		String val1 = "12345";
		String val2 = "EDCBA";
		
		//processing
		NAryNumber nary = new NAryNumber(N, characters);
		String result = nary.convFromDecToNAry(
			nary.convFromNAryToDec(val1) + nary.convFromNAryToDec(val2)
		);
		System.out.println(result);
	}
}

class NAryNumber {
	private int N;									//N value of N-ary
	private char[] characters;						// 0～N-Character corresponding to 1
	private HashMap<Character, Integer> numbers;	// 0～N-The number corresponding to the first letter

	public NAryNumber(int n, char[] c) {
		this.N = n;
		this.characters = c.clone();
		this.numbers = new HashMap<Character, Integer>();
		for (int i = 0; i < this.characters.length; i ++) {
			numbers.put(this.characters[i], i);
		}
	}
	public int convFromNAryToDec(String nAry) {
		int dec = 0;	//Value converted from N-ary to decimal
		for (int i = 0; i < nAry.length(); i ++) {
			//Find the sum in order from the 1st place
			dec += numbers.get(nAry.charAt(nAry.length() - 1 - i)) * Math.pow(N, i);
		}
		return dec;
	}
	public String convFromDecToNAry(int dec) {
		String nAryRev = "";
		//The order in which the remainder was sought(Reverse order)Convert to N-ary
		while (dec >= this.N) {
			int rem = dec % this.N;
			dec = (dec - rem) / N;
			nAryRev += this.characters[rem];
		}
		nAryRev += this.characters[dec];
		//Invert the string and then return
		return new StringBuffer(nAryRev).reverse().toString();
	}
}

So, this time I mainly implemented the conversion of $ n $ decimal number ⇔ decimal number. If possible, I would like to implement a process that can read the settings written in the text file as described above and calculate the formula entered from the console. We will work on these as future issues. If you have another chance, please get along with me.

Thank you for reading.

Digression: Image of class and encapsulation for me

Added on December 13 In the comments below, you have pointed out the interface. Please check it out.

It's a digression, but please forgive me.

As I wrote this article, I was wondering what classes and encapsulations were all about. Of course, I can look up those explanations in books and online, but when I was wondering if there was any way of thinking that would suit me, I came up with an example that I could personally understand. ..

When you were in elementary school or junior high school, you had the role of a XX committee member at school. Class representatives, library committee members, health committee members, etc. Naturally, there is no person named XX committee member. The true identity is Nantoka Taro, Nantoka Hanako, and other real people. So, let's think that the class __ refers to a __specific role like a library committee member, and the person or thing that actually plays that __ role is an entity (instance) __. For example, the reticent Yuki Nantoka, who always reads books quietly in the library and wears or does not wear glasses depending on the day, seems to be the entity of a class named Library Committee.

A little more delusional, there is a variable in the library committee class called the book lending list. This list is not visible to unauthorized persons for privacy reasons, so add the qualifier private. Instead, add the public qualifier to the method named "Show Lending List" to show the lending list of books only to special people such as teachers and other library members. By doing so, a process that causes a person (other programmer) who is not familiar with the work of the library committee to see the loan list by an unauthorized person (process that was not originally expected ⇒ can cause a bug) You can avoid the situation of writing (it will be an error if you write it). In this way, one of the ideas of encapsulation is to make variables and methods (called member variables and member methods) in the class inaccessible from outside the class and to decide how to refer to them. Department).

Further delusional, some of the library committee members are called the library committee members __Chief __, who are at the top of the library committee members in the school. If you create a class called Library Committee __Chief __ from scratch, there will be inefficiencies such as copying the variables and methods of the Library Committee (if the specifications of the book lending list change, the Library Committee will Both the class and the library committee __long__class must be rewritten as well!). Therefore, by creating a library committee __long __ class by inheriting the library committee class _, the variables and methods of the library committee class can be used without having to bother to write them. It feels like it's OK if you add only the role unique to long (such as managing the attendance of the library committee members).

Last but not least, if a role is what the class really is, it's important to give it a name that is easy for other programmers to understand what that role is. I always try to make cool English words, but usually the results are half-hearted. The NAryNumber class this time is also a product of that. By the way, conv in the method name is an abbreviation for convert, and Dec is an abbreviation for Decimal, but it is meaningless unless it is transmitted. Please note that such naming is not very good.

Thank you for reading to such a place.