Пянтичное: опять фибоначчи

[Slavandik]

16 в двоичной системе исчисления будет 10000, а в 16-чной будет 1.

Really?

[crypto5]

16 в двоичной системе исчисления будет 10000, а в 16-чной будет 1.

Really?

А что именно не так?

[venco]

16 в двоичной системе исчисления будет 10000, а в 16-чной будет 1.

Ага, щаз. В 16-ричной будет 10, причём нолик - четырёхбитный.

[crypto5]

16 в двоичной системе исчисления будет 10000, а в 16-чной будет 1.

Ага, щаз. В 16-ричной будет 10, причём нолик - четырёхбитовый.

Да, ошибся, но дело это не меняет?

[Интеррапт]

16 в двоичной системе исчисления будет 10000, а в 16-чной будет 1.

Really?

А что именно не так?

Да похоже ты опечатался (1 вместо 10).

[crypto5]

16 в двоичной системе исчисления будет 10000, а в 16-чной будет 1.

Ага, щаз. В 16-ричной будет 10, причём нолик - четырёхбитный.

Нолик будет столькибитным как вы закомпрессируете. Например в случае 2^27 что бы закодировать 2^27 вам не обязательно использовать многобитный ноль, можно закодировать попроще.

[crypto5]

16 в двоичной системе исчисления будет 10000, а в 16-чной будет 1.

Really?

А что именно не так?

Да похоже ты опечатался (1 вместо 10).

Да, согласен, лоханулся

[venco]

Нолик будет столькибитным как вы закомпрессируете. Например в случае 2^27 что бы закодировать 2^27 вам не обязательно использовать многобитный ноль, можно закодировать попроще.

Ну так и двоичные нолики можно закомпрессировать. Давайте уж сравнивать яблоки с яблоками.

[crypto5]

Нолик будет столькибитным как вы закомпрессируете. Например в случае 2^27 что бы закодировать 2^27 вам не обязательно использовать многобитный ноль, можно закодировать попроще.

Ну так и двоичные нолики можно закомпрессировать. Давайте уж сравнивать яблоки с яблоками.

Можно, таким образом вы перейдете из позизионной системы исчисления по основанию 2 к позиционной системе исчисления по основанию во сколько вы там закомпрессируете, например 2^27.

[АццкоМото]

Почему вы не можете сделать тоже самое для основания 2^27 или любого другого удобного числа?

Кэп подсказывает, что для любого основания, равного степени двойки для записи все равно потребуется ровно столько же битиков, как и для записи в двоичной системе
Или я не понял идею

16 в двоичной системе исчисления будет 10000, а в 16-чной будет 1.

Не 1, а 10. и шышнацытиричное 10 - это кагбэ 8 бит

[АццкоМото]

Можно, таким образом вы перейдете из позизионной системы исчисления по основанию 2 к позиционной системе исчисления по основанию во сколько вы там закомпрессируете, например 2^27.

Ну очевидно же, что для записи одной цифирки в такой системе нам потребуется аккурат 27 битиков. В чем пойнт-то?
Если бы мы знали, что вот именно в такой системе одни цифирки будут встречаться значительно чаще других... но вроде у нас нет таких знаний

[crypto5]

Можно, таким образом вы перейдете из позизионной системы исчисления по основанию 2 к позиционной системе исчисления по основанию во сколько вы там закомпрессируете, например 2^27.

Ну очевидно же, что для записи одной цифирки в такой системе нам потребуется аккурат 27 битиков. В чем пойнт-то?
Если бы мы знали, что вот именно в такой системе одни цифирки будут встречаться значительно чаще других... но вроде у нас нет таких знаний

В общем случае у нас да, нет таких знаний, в данном вроде как есть.

[АццкоМото]

Можно, таким образом вы перейдете из позизионной системы исчисления по основанию 2 к позиционной системе исчисления по основанию во сколько вы там закомпрессируете, например 2^27.

Ну очевидно же, что для записи одной цифирки в такой системе нам потребуется аккурат 27 битиков. В чем пойнт-то?
Если бы мы знали, что вот именно в такой системе одни цифирки будут встречаться значительно чаще других... но вроде у нас нет таких знаний

В общем случае у нас да, нет таких знаний, в данном вроде как есть.

Да? И какие же это цифры?
Не, я, конечно, не знаю, может, и так и всем это очевидно, но мне - нет.
Я только вижу, что последняя цифра в системе с основанием 2^27 будет ноль. Про остальные не вижу ничего
UPD. Перезарядил. Все верно - ноликов там будет под сраку

[crypto5]

Можно, таким образом вы перейдете из позизионной системы исчисления по основанию 2 к позиционной системе исчисления по основанию во сколько вы там закомпрессируете, например 2^27.

Ну очевидно же, что для записи одной цифирки в такой системе нам потребуется аккурат 27 битиков. В чем пойнт-то?
Если бы мы знали, что вот именно в такой системе одни цифирки будут встречаться значительно чаще других... но вроде у нас нет таких знаний

В общем случае у нас да, нет таких знаний, в данном вроде как есть.

Да? И какие же это цифры?
Не, я, конечно, не знаю, может, и так и всем это очевидно, но мне - нет.
Я только вижу, что последняя цифра в системе с основанием 2^27 будет ноль. Про остальные не вижу ничего

Ну вся эта дискуссия выросла из задачи про 2^(3^(4^(5^6))).
Вообще говоря если бы у меня в реальности появилась бы такая задача, я бы вообще скорее всего забил на позиционные системы, а пытался бы работать с исходным представлением: а^(b^(...)) и т.д.

[vopros]

Ну вся эта дискуссия выросла из задачи про 2^(3^(4^(5^6))).
Вообще говоря если бы у меня в реальности появилась бы такая задача

а что бы вы сделали, если бы она появилась на интервью ?
написали бы код? если б да то какой?

[crypto5]

Ну вся эта дискуссия выросла из задачи про 2^(3^(4^(5^6))).
Вообще говоря если бы у меня в реальности появилась бы такая задача

а что бы вы сделали, если бы она появилась на интервью ?
написали бы код? если б да то какой?

Я бы спросил в каком формате им это нужно, и для каких целей, что они потом с этим числом делать собираются, от этого наверное и зависело какой код писать.

[vopros]

Ну вся эта дискуссия выросла из задачи про 2^(3^(4^(5^6))).
Вообще говоря если бы у меня в реальности появилась бы такая задача

а что бы вы сделали, если бы она появилась на интервью ?
написали бы код? если б да то какой?

Я бы спросил в каком формате им это нужно, и для каких целей, что они потом с этим числом делать собираются, от этого наверное и зависело какой код писать.

спросить было нельзя, можно было только код написать.
мой вариант был таков. Он их устроил, но меня нет. А лучше не получается

Code: Select all

import java.math.BigInteger;

public class Test {

	/**
	 * Q.2 calc of 2^(3^(4^(5^6)))
	 */
	public static void main(String[] args) {
		calc();
	}

	static void calc() {
		int start = 6;
		BigInteger next = null;
		BigInteger power = new BigInteger(String.valueOf(start));
		for (; start > 2; start--) {
			next = new BigInteger(String.valueOf(start - 1));
			power = bigPower(next, power);
		}
	}

	static BigInteger bigPower(BigInteger num, BigInteger power) {
		BigInteger r = num;
		BigInteger counter = new BigInteger("1");
		while (!counter.equals(power)) {
			r = r.multiply(num);
			counter = counter.add(new BigInteger("1"));
		}
		return r;
	}
}

[crypto5]

Думаю в идеале вы сказали бы что мол число не поместится в памяти и программа бессмысленна. Ну и теоретически в степень можно возводить за логарифмическое время а не линейное как у вас.

[vopros]

Думаю в идеале вы сказали бы что мол число не поместится в памяти и программа бессмысленна. Ну и теоретически в степень можно возводить за логарифмическое время а не линейное как у вас.

это было первое, что я ответил, пораскинув мозгами.
возможно само решение, после этого было не так важно.
Но как возвести за логарифмическое время ? приведите пример пожалуйста

[crypto5]

Думаю в идеале вы сказали бы что мол число не поместится в памяти и программа бессмысленна. Ну и теоретически в степень можно возводить за логарифмическое время а не линейное как у вас.

это было первое, что я ответил, пораскинув мозгами.
возможно само решение, после этого было не так важно.
Но как возвести за логарифмическое время ? приведите пример пожалуйста

http://stackoverflow.com/questions/1014 ... powint-int

[vopros]

Думаю в идеале вы сказали бы что мол число не поместится в памяти и программа бессмысленна. Ну и теоретически в степень можно возводить за логарифмическое время а не линейное как у вас.

это было первое, что я ответил, пораскинув мозгами.
возможно само решение, после этого было не так важно.
Но как возвести за логарифмическое время ? приведите пример пожалуйста

http://stackoverflow.com/questions/1014 ... powint-int

это не то, так как ни степень, ни результат в int не влезают.

[crypto5]

Думаю в идеале вы сказали бы что мол число не поместится в памяти и программа бессмысленна. Ну и теоретически в степень можно возводить за логарифмическое время а не линейное как у вас.

это было первое, что я ответил, пораскинув мозгами.
возможно само решение, после этого было не так важно.
Но как возвести за логарифмическое время ? приведите пример пожалуйста

http://stackoverflow.com/questions/1014 ... powint-int

это не то, так как ни степень, ни результат в int не влезают.

Но принцип можно ведь перенести на бигинтеджер?

[vopros]

Думаю в идеале вы сказали бы что мол число не поместится в памяти и программа бессмысленна. Ну и теоретически в степень можно возводить за логарифмическое время а не линейное как у вас.

это было первое, что я ответил, пораскинув мозгами.
возможно само решение, после этого было не так важно.
Но как возвести за логарифмическое время ? приведите пример пожалуйста

http://stackoverflow.com/questions/1014 ... powint-int

это не то, так как ни степень, ни результат в int не влезают.

Но принцип можно ведь перенести на бигинтеджер?

чтобы log(n) нельзя. попробуйте

[crypto5]

Code: Select all

import java.math.BigInteger;


public class BigintPower {
	public static void main(String[] args) {
		System.out.println(pow(BigInteger.valueOf(2), BigInteger.TEN));
	}

	static BigInteger pow(BigInteger n, BigInteger p) {
		BigInteger res = BigInteger.ONE;
		while(!p.equals(BigInteger.ZERO)) {
			if(p.testBit(0)) res = res.multiply(n);
			p = p.divide(BigInteger.valueOf(2));
			n = n.multiply(n);
		}
		return res;
	}
}

O(log(n)) относительно операций умножения бигинтеджеров понятно.

[vopros]

Code: Select all

import java.math.BigInteger;


public class BigintPower {
	public static void main(String[] args) {
		System.out.println(pow(BigInteger.valueOf(2), BigInteger.TEN));
	}

	static BigInteger pow(BigInteger n, BigInteger p) {
		BigInteger res = BigInteger.ONE;
		while(!p.equals(BigInteger.ZERO)) {
			if(p.testBit(0)) res = res.multiply(n);
			p = p.divide(BigInteger.valueOf(2));
			n = n.multiply(n);
		}
		return res;
	}
}

O(log(n)) относительно операций умножения бигинтеджеров понятно.

завтра обмозгую