Форум программистов, компьютерный форум CyberForum.ru

Перевод кода с Java - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Севак
любитель покушать
 Аватар для Севак
674 / 625 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
06.07.2013, 20:46     Перевод кода с Java #1
Здравствуйте! Есть код на java, который работает недостаточно быстро, для его ускорения решил переписать его на c++, вот что вышло, помогите исправить реализацию на c++ или укажите на ошибки, буду благодарен!

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
    public static final BigInteger one = BigInteger.ONE;
    public static final BigInteger minusOne = BigInteger.valueOf(-1);
    public static final BigInteger two = BigInteger.valueOf(2);
    public static final BigInteger three = BigInteger.valueOf(3);
    public static final BigInteger mod = BigInteger.valueOf(1000000007);
 
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        System.out.println(G(n));
    }
 
    public static BigInteger G(int n) {
        if(n % 2 == 0) {
            return two.shiftLeft(n).add(one).divide(three).mod(mod).subtract(one);
        } else {
            return two.shiftLeft(n).add(minusOne).divide(three).mod(mod);
        }
    }
 
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <stdint.h>
#include <math.h>
 
using namespace std;
 
int64_t G(int64_t n, int64_t mod) {
    if(n % 2 == 0) {
        return (((2 << n) + 1)/3) % mod - 1;
    } else {
        return (((2 << n) - 1)/3) % mod;
    }
}
 
 
int main() {
    int64_t n;
    int64_t mod = 1000000007;
 
    cin >> n;
    cout << G(n, mod);
 
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.07.2013, 20:46     Перевод кода с Java
Посмотрите здесь:

C++ Перевод кода на с++
Перевод кода с Java на С++ C++
C++ Перевод кода с Java
перевод кода с C# на C++ C++
C++ Перевод кода
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.07.2013, 20:47     Перевод кода с Java #2
Это ж одно и тоже, нет?
Севак
любитель покушать
 Аватар для Севак
674 / 625 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
06.07.2013, 20:48  [ТС]     Перевод кода с Java #3
p.s.: 1 <= n <= 1_000_000_000
в реализации c++ на больших числах выдает 0

Добавлено через 26 секунд
Dani, я знаю, но работает некорректно
Dani
06.07.2013, 20:52
  #4

Не по теме:

Цитата Сообщение от Севак Посмотреть сообщение
Dani, я знаю, но работает некорректно
нет, здесь был один и тот же код на Java и там и там.

Севак
любитель покушать
 Аватар для Севак
674 / 625 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
06.07.2013, 20:53  [ТС]     Перевод кода с Java #5
Dani,

Не по теме:

сначала нечаянно не то вставил

Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.07.2013, 21:14     Перевод кода с Java #6
Цитата Сообщение от Севак Посмотреть сообщение
p.s.: 1 <= n <= 1_000_000_000
в реализации c++ на больших числах выдает 0
так и должно быть, http://www.cyberforum.ru/cgi-bin/latex.cgi?2^{1\,000\,000\,000} ни в один тип данных не влезет, вот и получаете нули, n не может превышать значения 62, так как там еще 2-ка есть
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
06.07.2013, 21:15     Перевод кода с Java #7
Цитата Сообщение от Севак Посмотреть сообщение
p.s.: 1 <= n <= 1_000_000_000
С помощью int64 2109 конечно не представишь
Севак
любитель покушать
 Аватар для Севак
674 / 625 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
06.07.2013, 21:18  [ТС]     Перевод кода с Java #8
Всем спасибо, буду думать дальше!
Belfegor
06.07.2013, 21:20
  #9

Не по теме:

в с++ нет готового типа, надо писать с длинной арифметикой

Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.07.2013, 21:24     Перевод кода с Java #10
да, только длинная арифметика должна быть очень продуманной, а то возникнет такая же проблема, как здесь
Возведение двойки в миллиардную степень
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.07.2013, 21:27     Перевод кода с Java #11
Тут явно: обычная длинка + двоичное возведение в степень

Добавлено через 1 минуту
Возведение в степень будет за логарифм, итого 31 перемножение.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.07.2013, 21:30     Перевод кода с Java #12
Цитата Сообщение от Dani Посмотреть сообщение
Возведение в степень будет за логарифм, итого 31 перемножение.

Не по теме:

это все понятно, только в десятичный вид перевести все это не так просто. это для задачи из другой ветки

Севак
любитель покушать
 Аватар для Севак
674 / 625 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
06.07.2013, 21:32  [ТС]     Перевод кода с Java #13
насчет двоичного возведения в степень:
правильно ли я помню что 2^n == 1 и n нулей?
вот еще на что наткнулся
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.07.2013, 21:33     Перевод кода с Java #14
Цитата Сообщение от Севак Посмотреть сообщение
насчет двоичного возведения в степень:
правильно ли я помню что 2^n == 1 и n нулей?
правильно
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.07.2013, 21:35     Перевод кода с Java #15
Thinker, что? переводить не нужно ничего.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.07.2013, 21:37     Перевод кода с Java #16
Цитата Сообщение от Dani Посмотреть сообщение
Thinker, что? переводить не нужно ничего.
я про эту задачу
Возведение двойки в миллиардную степень
немного похожая задача
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.07.2013, 21:39     Перевод кода с Java #17
Двоичное возведение в степень строится по следующему принципу. Есть функция http://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b) , если b - четное, то из числа http://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b) можно извлечь корень, получается, что http://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b) = {(power(a, b/2))}^{2} . Если же b нечетное, то http://www.cyberforum.ru/cgi-bin/latex.cgi?power(a, b) = power(a, b-1) * a . При b = 1 , результат равен a.

Ничего кроме умножения и рекурсивного спуска.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.07.2013, 21:42     Перевод кода с Java #18
Dani, это да, очень даже понятно но та задача даже так быстро не решается. я там оценил время работы алгоритма. если использовать двоичное возведение, то оно даст выигрыш не более чем в 10 раз и время работы будет сутками исчисляться
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.07.2013, 21:45     Перевод кода с Java #19
Хм... щас... может Карацуба
http://www.wolframalpha.com/input/?i=2%5E1000000000
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2013, 21:46     Перевод кода с Java
Еще ссылки по теме:

Перевод кода С# на C++ C++
C++ Перевод кода из java в С++
C++ Перевод кода с Java на С++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.07.2013, 21:46     Перевод кода с Java #20
Цитата Сообщение от Dani Посмотреть сообщение
Хм... щас... может Карацуба
умножение по методу Карацубы тоже хорошо известная и полезная вещь, но увы...
Yandex
Объявления
06.07.2013, 21:46     Перевод кода с Java
Ответ Создать тему
Опции темы

Текущее время: 05:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru