Форум программистов, компьютерный форум 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, 21:49     Перевод кода с Java #21
http://habrahabr.ru/post/124258/

Карацуба дает сложность http://www.cyberforum.ru/cgi-bin/latex.cgi?{n}^{{log}_{2}3} от числа цифр. Двоичное возведение дает 31. Это скрытая константа, что вполне приемлемо. Итого 3.0103 * 10^8
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Севак
любитель покушать
 Аватар для Севак
674 / 625 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
06.07.2013, 21:53  [ТС]     Перевод кода с Java #22
Я тут посмотрел, со своим Java'вским кодом на 1_000_000_000 получаю такие результаты:

1000000000
Time: 1.283588667 sec
93750000
Мне нужно уложиться в 1 секунду, поэтому пойду-ка я оптимизировать его, наверное больше времени потрачу на поиск решения на c++
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.07.2013, 21:54     Перевод кода с Java #23
ладно, может зря отверг эту идею, думал есть какой то красивый мат.метод
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.07.2013, 21:57     Перевод кода с Java #24
Севак, там есть реализация Карацубы на С++ и добавь к этому двоичное возведение в степень. Буду признателен, если скажешь, за сколько выполнится.

Добавлено через 1 минуту

Не по теме:

Цитата Сообщение от Thinker Посмотреть сообщение
ладно, может зря отверг эту идею, думал есть какой то красивый мат.метод
получается, только хардкор

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

Не по теме:

хорошо только наверное не сегодня, с с++ 2ой день только работаю и то по необходимости, а задачу нужно сделать срочно

diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.07.2013, 03:34     Перевод кода с Java #26
Вроде ж все тривиально
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
25
26
27
28
29
30
31
#include <iostream>
 
unsigned powmod(unsigned base, unsigned exp, unsigned modulo) //returns (base ^ exp) % modulo
{
    unsigned res = 1;
    
    while (exp != 0) 
    {
        if ((exp & 1) != 0)
        {
            res = (1ll * res * base) % modulo;
        }
        
        base = (1ll * base * base) % modulo;
        exp >>= 1;
    }
    
    return res;
}
 
int G(int n, int modulo) 
{
    return (-~powmod(2, n + 1, modulo) - 2 * (n & 1)) * 333333336ll % modulo + ~n % 2;
}
 
int main()
{
    int n;
    std::cin >> n;
    std::cout << G(n, 1000000007);
}
Севак
любитель покушать
 Аватар для Севак
674 / 625 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
07.07.2013, 11:56  [ТС]     Перевод кода с Java #27
diagon,

Не по теме:

я б тебя прям расцеловал (ничего плохого не подумай)! спасибо большое!

Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
07.07.2013, 12:05     Перевод кода с Java #28
Есть код на java, который работает недостаточно быстро, для его ускорения решил переписать его на c++
Совет на будущее. Прежде чем что-то оптимизировать, нужно определить bottleneck'и, ты ведь даже не знаешь, в чем именно проблема. Может быть она в твоих руках? :-)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2013, 12:06     Перевод кода с Java
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Севак
любитель покушать
 Аватар для Севак
674 / 625 / 106
Регистрация: 25.09.2011
Сообщений: 1,313
07.07.2013, 12:06  [ТС]     Перевод кода с Java #29
Герц, может быть
Yandex
Объявления
07.07.2013, 12:06     Перевод кода с Java
Ответ Создать тему
Опции темы

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